PS1, Part 4: Putting It All Together

👈 Back to problem set index.

Problem Nine: Proof Critiques

One of the best ways to improve your proof writing is to do some proof reading. In doing so, you’ll get a much better perspective on why certain stylistic conventions matter, both in the positive sense, (“wow, that’s so easy to read!”) and in the negative sense (“I can’t make heads or tails of this!”). You’ll also get practice tracing through mathematical arguments, which will help expand your repertoire of techniques and give you a better sense of what details to focus on in your own reasoning.

We’ve curated three proofs for you to review. Read these proofs, and for each one, do the following:

• Critique its style. Our Proofwriting Checklist contains specific details to review in any proof. Go through the checklist one item at a time, identifying any style errors and explaining each.
• Critique its reasoning. Are the arguments given by these proofs correct? If there are logic errors, point them out and demonstrate why they’re incorrect. Then, determine whether the theorem being proved is even true in the first place. After all, you can prove anything using faulty logic!

Complete the critique for each of the three proofs by filling out the table below:

1. Critique this proof about parities (the parity of a number is whether it’s even or odd.)

   Theorem: The sum of an even integer and an odd integer is odd.

   Proof: This proof will talk about adding together different kinds of numbers. An even integer is an integer that can be written as $2k$ for some integer $k\text.$ Therefore, $m = 2k\text.$ Similarly, an odd integer is one that can be written as $2k+1$ for some integer $k$. So $n = 2k+1\text.$ $m + n = 2k + 2k + 1 = 4k + 1\text.$ Therefore $m + n$ is odd. $\qed$

2. Critique this proof about natural numbers.

   Theorem: Every natural number is odd.

   Proof: Assume for the sake of contradiction that every natural number is even. In particular, that would mean that $137$ is even. Since $137 = 2 \cdot 68 + 1$ and $68$ is a natural number, we see that $137$ is odd. We know that there is no integer $n$ where $n$ is both odd and even. However, $n = 137$ is both even and odd. This is impossible. We’ve reached a contradiction, so our assumption must have been wrong. Therefore, every natural number is odd. $\qed$

3. Critique this proof about modular arithmetic.

   Theorem: If $n$ is an integer and $n \equiv_2 0$, then $n \equiv_4 0\text.$

   Proof: We will prove the contrapositive of this statement and show that if $n$ is an integer where $n \equiv_4 0\text,$ then $n \equiv_2 0\text.$ Since $n \equiv_4 0\text,$ we know $n = 0 + 4q\text.$ This in turn tells us that $n = 2(2q)\text,$ so there is an integer $m$ such that $n = 2m$. Consequently, we see that $n = 0 + 2m\text,$ and so $n \equiv_2 0\text,$ as required. $\qed$

Problem Ten: Sums of Cubes

In a previous problem, we talked about the four-square theorem: every natural number is the sum of four squares. In this problem, you will work through a series of smaller exercises that builds up to a proof of the following fact: every integer can be written as the sum of five cubes. (Here, a cube is an integer raised to the third power.) For example, we can write $103$ like this:

We'll begin with the following result, which says that every integer that's a multiple of six can be written as the sum of four cubes.

1. Prove for all integers $n$ that there are integers $v\text,$ $w\text,$ $x\text,$ and $y$ such that $6n = v^3 + w^3 + x^3 + y^3\text.$

   This result is reminiscent of the theorem from lecture that every odd integer is the difference of two squares. In proving that result, we began by first looking for a pattern in specific, small odd integers. Once we spotted the pattern, our proof then justified why that pattern would work for all odd integers, not just the ones we tried. So before you begin writing this proof, take some time to explore and see if you can spot a pattern. We recommend that, before you start writing the proof, you find a way to fill in these blanks:

   \[\begin{array}{rcccc} 0 &=& 6 \cdot \left(\blank\right) &=& \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3\text. \\ 6 &=& 6 \cdot \left(\blank\right) &=& \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3\text. \\ 12 &=& 6 \cdot \left(\blank\right) &=& \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3\text. \\ 18 &=& 6 \cdot \left(\blank\right) &=& \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3\text. \\ \end{array}\]

   There are many ways you can fill these blanks. Since you are looking for a pattern, we recommend seeing if you can find a way to fill the blanks so that a clear trend emergees across the rows and columns. Some options generalize nicely into clear patterns. Others do not. You won't know which way to fill the blanks in will lead to a pattern and which won't without patiently exploring lots of options. Don't be afraid about going down a dead end - it's okay if some of the choices you come up with don't end up getting used.

   Once you think you've found a pattern, make sure you can generalize the pattern by succinctly filling in the following blanks in terms of $n\text:$

   We can write $6n = \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3 + \left(\blank\right)^3\text.$

   At that point, you've identifed a generalizable pattern, and you will be in a good spot to begin writing a formal proof based on that pattern. Your proof will likely be fairly short and will simply justify why your pattern works.

Next, we'll need a result about modular arithmetic.

2. Prove for all integers $x$ that $x^3 \equiv_6 x\text.$ We recommend that you use a proof by cases based on the following fact: for every integer $n\text,$ there are integers $q$ and $r$ where $n = 6q + r$ and $r \in \set{0, 1, 2, 3, 4, 5}\text.$

   To prove that $x^3 \equiv_6 x\text,$ you need to find an integer $m$ where $x^3 = x + 6m\text.$ You might find it easier to regroup these terms and instead find a choice of $m$ where $x^3 - x = 6m\text.$ There are many different ways you can proceed from there, some of which are easier than others. You won't know which routes are easier or harder until you try them.

   As in the previous problem on modular arithmetic, make sure not to start with $x^3 - x = 6m$ in your proof and then simplify. That's perfectly acceptable for scratch work, but in a written proof the expectation is that you only work with known equalities. You are welcome to start with $x^3 - x$ by itself and to simplify that expression, or to propose a concrete choice of $m\text,$ start with $6m\text,$ and simplify that to $x^3 - x\text.$ In your scratch work, however, it is perfectly acceptable to start with $x^3 - x = 6m$ and simplify things from there, since at that point you're scouting out options rather than presenting a formal mathematical argument.

   You may find yourself needing to use different lines of reasoning based on what the value of $r$ is. What style of proof did we cover in lecture that works well for situations like these?

   There are many different ways to prove this. Some of the following pieces of advice may be useful depending on your approach:

   • If you have a polynomial in $x$ and have an equation of the form $x = \blank\text,$ you don't need to substitute $\blank$ in for $x$ everywhere you see $x\text.$ It might be cleaner if you don't. For example, if we know that $x = 4y + 2\text,$ it's easiest to show that $x(x+2)(x+4)$ is a multiple of four by rewriting it as $x(4y+4)(x+4) = 4x(y + 1)(x + 4)$ rather than by substituting $x = 4y + 2$ everywhere to get $(4y + 2)(4y + 4)(4y + 6)$ and then regrouping that as $4(4y+2)(y+1)(4y+6)\text.$

   • If you have a messy polynomial that is largely a multiple of some number, it's a lot easier if you introduce a new variable standing in for part of that polynomial. For example, if you came across something like $16x^4 + 120x^3 + 44x^2 + 32x + 1$ and were interested in multiples of four, you might want to rewrite this as $4(4x^4 + 30x^3 + 11x^2 + 8x) + 1$ and then define a new value $y = 4x^4 + 30x^3 + 11x^2 + 8x$ to write the entire expression as $4y + 1\text.$

   And, as in the previous problem, you aren't expected to immediately see why this is true. A bit of trial and error might be necessary, and that's okay! Don't be afraid to back up and try something else if your initial approach doesn't seem to be leading anywhere.

Now, it's time to put it all together.

3. Prove that for every integer $n\text,$ there are integers $v\text,$ $w\text,$ $x\text,$ $y\text,$ and $z$ such that $n = v^3 + w^3 + x^3 + y^3 + z^3\text.$

   This one is mostly about putting all the pieces together. Feel free to cite the results from the previous two parts of this problem (for example, you might say something like "by our result from part (i), we know that there are integers $v\text,$ $w\text,$ $x\text,$ and $y$ such that $6p = v^3 + w^3 + x^3 + y^3$")

Here's a surprising fact: while it's known that every integer is the sum of five cubes, it's not yet known whether all integers are the sum of four cubes. No one has ever found an integer that can't be written as the sum of four cubes, and no one knows whether one exists. It might seem surprising that we don't know this - it doesn't seem like it should be that hard to figure this out! - and yet that's the present state of human knowledge. As you start studying theoretical computer science, you'd be surprised just how little we know!

Sums of three cubes have even wilder properties; we'll talk about that later in the quarter when discussing the limits of what computers can do.