Sums of Squares

Today we'll look at an activity that explores different aspects of expressing a positive integer as a sum of squares.


Setup

A nice manipulative for this activity would be some sort of unit square that can be used to make larger squares on a tabletop. Square color tiles are a great option. The square tiles from a set of pattern blocks work, if you happen to have a bunch of them.

We'll ask it in a few different ways, but the core question of this activity is pretty simple:

Given \(t\) tiles, can we arrange them into \(s\) squares?

By a square, we mean an \(n \times n\) grid of \(n^2\) tiles. While students don't need to understand multiplication to do this activity, you might want to show them some examples to distinguish this sort of square grid from the outline of an \(n \times n\) square and other square-ish shapes.


Initial Questions

Here are some puzzles to get the ball rolling:

  1. Given \(9\) tiles, can you find a way to arrange them into:

    • \(1\) square?
    • \(2\) squares?
    • \(3\) squares?
    • \(4\) squares?
    • \(5\) squares?

    What other numbers of squares can be made from \(9\) tiles?

  2. What about with \(10\) tiles? \(11\)? \(12\)?

  3. Given \(21\) tiles, what's the least number of squares you can make?

  4. What about with \(22\) tiles? \(23\)? \(24\)?

More broadly, here are some questions to focus on:

  • Is there a way to predict the minimum number of squares that can be made from \(n\) tiles? (If not for all \(n\), what about special values of \(n\)?)

  • Is there a way to predict the numbers of squares that can be made from \(n\) tiles? (If not for all \(n\), what about special values of \(n\)?)


Explorations

Here are some things that students might discover or be guided into thinking about:

  • A basic question is which numbers of tiles can be made into a single square. For mature students this will be obvious, but for students who don't know how to multiply, this poses an interesting challenge. If you try to arrange tiles into a square, it's helpful to have a size in mind. One way to think about it is to ask whether you can make a \(1 \times 1\), then \(2 \times 2\), then \(3 \times 3\), and so on. Students might stumble upon the idea of "growing" a square to get the next one by building along the border. Below is a way that someone might demonstrate that \(14\) tiles cannot be arranged into a square:

    Along the way to seeing that \(14\) tiles falls short of making a \(4 \times 4\) square by "growing," we find that \(1\) forms a \(1 \times 1\), \(4\) form a \(2 \times 2\), and \(9\) form a \(3 \times 3\).

    A couple related concepts to ponder:

    • The relationship between subsets and areas: A larger square requires more tiles than a smaller square.

    • Uniqueness: If a square can be made from \(t\) tiles, there's only one way to make it.

    Just noting that there is a sequence of square numbers and finding the first several is a great opening exploration.

  • For less mathematically mature students, I would play mostly in the realm of making different arrangements of squares from a set number. For example, trying to "catch them all" by finding all of the ways that \(9\) tiles can be made into squares could be a fun challenge. Someone can record them so that each student's contributions are celebrated and added to the record, with students encouraged to find new arrangements. Here are some answers to the example questions for \(9\) and \(10\):

    For a lot of low numbers, the partitions into squares will follow pretty predictable patterns that students might guess if they have them all in front of them. Since adding one \(1 \times 1\) square to a partition of \(n\) into squares gives a partition of \(n+1\) into squares, we will always see these sorts of "survivor" partitions like we see going from \(9\) to \(10\). We have to wait until \(12\) to see a genuinely new partition into squares that is not derived by adding \(1 \times 1\) squares to existing partitions:

    These survivor partitions provide some predictability for the numbers of squares we might be able to make.

  • The problem of the least number of squares that \(n\) can be partitioned into is a classic problem in number theory. When I do explorations like this, I'll often create a record board where students collaborate to find the best for different values and beat the current records. For example, one student might find that \(29 = 1+9+16\) before another student notes \(29 = 4+25\), reducing the record for \(29\) from \(3\) to \(2\). Here is a table of best possible results for small numbers. It's nonstandard, but just to have something to refer to, we'll call the minimum number of squares achievable for \(n\) its extremal square partition number (ESPN):

    \(n\)ESPNExample\(n\)ESPNExample
    \(1\)\(1\)\(1\)\(21\)\(3\)\(16+4+1\)
    \(2\)\(2\)\(1+1\)\(22\)\(3\)\(9+9+4\)
    \(3\)\(3\)\(1+1+1\)\(23\)\(4\)\(9+9+4+1\)
    \(4\)\(1\)\(4\)\(24\)\(3\)\(16+4+4\)
    \(5\)\(2\)\(4+1\)\(25\)\(1\)\(25\)
    \(6\)\(3\)\(4+1+1\)\(26\)\(2\)\(25+1\)
    \(7\)\(4\)\(4+1+1+1\)\(27\)\(3\)\(25+1+1\)
    \(8\)\(2\)\(4+4\)\(28\)\(4\)\(25+1+1+1\)
    \(9\)\(1\)\(9\)\(29\)\(2\)\(25+4\)
    \(10\)\(2\)\(9+1\)\(30\)\(3\)\(25+4+1\)
    \(11\)\(3\)\(9+1+1\)\(31\)\(4\)\(25+4+1+1\)
    \(12\)\(3\)\(4+4+4\)\(32\)\(2\)\(16+16\)
    \(13\)\(2\)\(9+4\)\(33\)\(3\)\(25+4+4\)
    \(14\)\(3\)\(9+4+1\)\(34\)\(2\)\(25+9\)
    \(15\)\(4\)\(9+4+1+1\)\(35\)\(3\)\(25+9+1\)
    \(16\)\(1\)\(16\)\(1\)\(1\)\(36\)
    \(17\)\(2\)\(16+1\)\(37\)\(2\)\(36+1\)
    \(18\)\(2\)\(9+9\)\(38\)\(3\)\(36+1+1\)
    \(19\)\(3\)\(9+9+1\)\(39\)\(4\)\(36+1+1+1\)
    \(20\)\(2\)\(16+4\)\(40\)\(2\)\(36+4\)

    Some things that stick out about the ESPN column:

    • All values so far are \(1\), \(2\), \(3\), or \(4\).

    • \(1\) and \(4\) seem to be much rarer than \(2\) and \(3\).

    • There is a spacing pattern to the \(1\)'s that can be inferred by counting the the number of entries until the next \(1\). You might be able to relate this to our "growing" method for finding the next square

      \[ 1 + 3 + 5 + ... + (2n-1) = n^2 \]

      and the algebraic relation

      \[ n^2 + (2n+1) = (n+1)^2 \]

      Since this ever-widening spacing continues, the numbers with ESPN \(1\) (i.e., square numbers) get rarer and rarer.

    • The values of \(n\) we've seen with ESPN \(4\) have all been odd except for \(28\). If we rule out \(28\), they seem to form an arithmetic sequence spaced \(8\) apart.

  • Some strategies for finding the ESPN of an integer:

    • If \(n\) is a perfect square decides whether its ESPN can be \(1\).

    • If \(n\) is not a perfect square, we can subtract squares from it and see if the difference is a square. If so, then ESPN is \(2\). (When \(n\) is large, this is much quicker than adding pairs of squares and checking if their sum is \(n\).)

    • If \(n\) is not a square or sum of two squares, finding its ESPN computationally is more nuanced. One approach combines the two ideas above. If we know the ESPN values for \(1\) through \(n-1\), then to find it for \(n\) we first decide whether \(n\) is a square. If it is, its ESPN is \(1\). If not, we then find the least of all ESPN values for the numbers \(n-k^2\), which we'll call \(m\). The ESPN for \(n\) will then be \(m+1\).

  • If one restricts their scope to the integers with ESPN \(\leq 2\), a more subtle observation is that if two of those numbers are multiplied, the result again has ESPN \(\leq 2\). If students are versed in algebra, this can be an interesting idea to explore. It's easy to see the product of two square numbers is again a square. If \(m = a^2 + b^2\) and \(n = c^2\), then

    \[ mn = (a^2+b^2)(c^2) = (ac)^2 + (bc)^2. \]

    The more surprising case is if \(m = a^2 + b^2\) and \(n = c^2+d^2\), then

    \[ \begin{eqnarray*} mn & = & (a^2 + b^2)(c^2+d^2) \\ & = & (ac)^2 + (bc)^2 + (ad)^2 + (bd)^2 \\ & = & (ac)^2 - 2(ac)(bd) + (bd)^2 + (ad)^2 + 2(ad)(bc) + (bc)^2 \\ & = & (ac-bd)^2 + (ad+bc)^2 \end{eqnarray*} \]

    Figuring out how to wrestle \( (a^2 + b^2)(c^2+d^2) \) into such a sum of two squares is a nice problem. This is known as the Brahmagupta–Fibonacci identity.

  • If we consider the numbers with ESPN \(\leq 4\), we can similarly show a product of two of them again has ESPN \(\leq 4\) by a similar algebraic identity. Advanced students might like to tackle this one, but it's much tougher! It can be shown that

    \[ (a^2+b^2+c^2+d^2)(e^2+f^2+g^2+h^2) \] equals \[ (ae-bf-cg-dh)^2 + (af+be+ch-dg)^2 + (ag-bh+ce+df)^2 + (ah+bg-cf+de)^2 \]

    so letting some of these variables be \(0\) whenever working with a sum of fewer than \(4\) squares establishes the result in all cases. The identity above is known as Euler's four-square identity.

  • If students are comfortable thinking about modular arithmetic or forms related to their remainders, then one standard trick they may know is to look at squares \(\mod 4)\). Since all integers have the form \(4k\), \(4k+1\), \(4k+2\), or \(4k+3\), the equations

    \[ \begin{eqnarray*} (4k)^2 & = & 4(4k^2), \\ & & \\ (4k+1)^2 & = & 4(4k^2+2k)+1 \\ & & \\ (4k+2)^2 & = & 4(4k^2+4k+1) \\ & & \\ (4k+3)^2 & = & 4(4k^2+6k+2)+1 \end{eqnarray*} \]

    show that all squares have the form \(4m\) or \(4m+1\). In particular, two of them cannot sum to a number of the form \(4m+3\), so any number with the form \(4m+3\) must have ESPN \(3\) or \(4\).

  • While we won't prove them here, some relevant results we've been circling are

    • Lagrange's four-square theorem: Every positive integer can be written as a sum of \(4\) or fewer squares.

      Though we didn't go very high in our table, this is what will ensure we never see an ESPN value of \(5\) or greater!

    • Legendre's three-square theorem: A positive integer can be written as a sum of \(3\) or fewer squares if and only if it does not have the form \(4^j (8k+7)\).

      This explains the strange pattern we saw for numbers with ESPN \(4\) having the form \(8k+7\) except \(28\), which is the least example of a number of the form \(4^j (8k+7)\) with \(j \neq 0\).

    • The sum of two squares theorem: A positive integer can be written as a sum of \(2\) or fewer squares if and only if its prime decomposition contains no factor of the form \(p^j\), where \(p\) is a prime of the form \(4k+3\) and \(j\) is odd.

    These three results provide a framework for deciding the ESPN of an integer \(n\) from its prime factorization.

    While we didn't look at primes explicitly, based on the above results we can put primes into three buckets:

    • \(p\) has ESPN \(2\) if \(p = 2\) or \(p = 4k+1\)
    • \(p\) has ESPN \(3\) if \(p = 8k+3\)
    • \(p\) has ESPN \(4\) if \(p = 8k+7\)

    These patterns are not terrible to pick out with enough evidence, but the irregularity of the primes means that the student would need a pretty good command of modular arithmetic or at least remainders.


Wrap-Up Questions

  • What was a good strategy for telling when a given number of tiles couldn't be made into a single square? What about when they couldn't be made into two squares?

  • Did you find any interesting patterns? Can you explain any of them?


    • Extensions

    • With unit cubes or as a pencil and paper activity, one could explore the next dimension of this problem:

      • What are the ways to express \(n\) as a sum of cubes?

      • What is the minimum number of cubes that could be made from \(n\) unit cubes?

      The latter question is part of Waring's problem.

    • Instead of making squares, one could instead made triangles:

      • What are the ways to express \(n\) as a sum of triangular numbers?

      • When writing \(n\) as a sum of triangular numbers, what is the minimum number of triangles required?

      If you opt for a manipulative, you have to be a little more careful here. For example, triangles from a pattern block set might lull you into making triangles from triangles, but the number of small triangles in a large triangle is again a square number, not a triangular number. Opt for figures like on the left below, not the one on the right.

      Gauss proved you never need more than three triangular numbers, but students might discover this conjecture for themselves and try to decide when \(1\) or \(2\) suffice. More broadly, this relates to Cauchy's theorem on polygonal numbers.


    This post was sponsored by the Julia Robinson Mathematics Festival

    Comments

    Post a Comment

    Popular posts from this blog

    Modular Origami with Sonobe Units

    The other month, I volunteered at Seattle Universal Math Museum's corner of Free First Thursdays at the Museum of Flight. Part of this was helping kids make origami paper airplanes, which reminded me of some origami challenges I used to give students. I'll present one of my favorite arcs here.
    Read more

    Instant Insanity

    Today we'll look at an old puzzle that has gone by many names over the centuries, my favorite name being "The Great Tantalizer." The most popular recent iteration was Parker Brothers' "Instant Insanity," so that's what most people call it. We'll look at some variations that let students explore how this puzzle might be easy (or at least easier ), hard, or impossible.
    Read more