Posted by Jason Polak on 03. June 2018 · 2 comments · Categories: elementary · Tags:

The sum of squares of two integers can be an integer. For example, $3^2 + 4^2 = 25^2$. Those are also the legs of a right-angle triangle. This example is special in that the numbers $3$ and $4$ are consecutive integers!

Can you find a sum of squares of three consecutive integers that make a square?

No, it's not possible. If $n$ is any integer, then the sum
$$n^2 + (n+1)^2 + (n+2)^2 = 3n^2 + 6n + 5.$$
Now, modulo three, any number squared is either 0 or 1. But this polynomial always outputs integers that are 2 mod 3. Therefore, the sum of three consecutive integers cannot be a perfect square.

Exercise: prove that the sum of squares of four consecutive integers cannot be a perfect square.

Maybe, you might be inclined to think that 2 is somehow special, and that a sum of squares of $k$ consecutive integers cannot be a perfect square if $k \gt 2$. But then you would be surprised at this sum of squares of fifty consecutive integers:
$$7^2 + 8^2 + 9^2 + \cdots + 55^2 + 56^2 = 60025 = 245^2.$$
Cool, right? This is by no means the smallest example. Here is another example of 407 consecutive integers:

$$183^2 + 184^2 + \cdots + 589^2 = 8140^2.$$

But are there infinitely many such examples?

Posted by Jason Polak on 23. May 2018 · Write a comment · Categories: elementary · Tags: ,

Consider the following series:
\begin{align*}
a_1 &= \frac{4}{3}\\
a_2 &= \frac{4}{3}\frac{9}{8}\\
&\vdots\\
a_n &= \frac{4}{3}\frac{9}{8}\cdots\frac{(n+1)^2}{(n+1)^2-1}
\end{align*}
In other words, $a_n$ is the product of all the numbers of the form $n^2/(n^2 – 1)$ for $n=2,\dots, n+1$.

Does $\lim_{n\to\infty} a_n$ exist? More »

Posted by Jason Polak on 23. November 2017 · 2 comments · Categories: elementary · Tags:

The smallest number paradox goes like this: consider the natural numbers: 0,1,2,3,… . Each can be specified by a string of characters. For example, "0" itself specifies 0. However, on my computer there are only finitely many bits. Therefore, only finitely many numbers can be specified as a string on my computer. In other words, there are some very huge numbers that just cannot be represented as a string on my computer. Now, the string doesn't have to be the longhand decimal expansion. For example, I might write "200!" for the number

7886578673647905035523632139321850622951359776871732632947425332443594499
6340334292030428401198462390417721213891963883025764279024263710506192662
4952829931113462857270763317237396988943922445621451664240254033291864131
2274282948532775242424075739032403212574055795686602260319041703240623517
0085879617892222278962370389737472000000000000000000000000000000000000000
0000000000

Because the natural numbers are well-ordered, there exists a smallest natural number $N$ that cannot be specified a a string on my computer. But wait, what about "the smallest natural number that cannot be represented as a string on my computer"? That string describes $N$. So there's the paradox: I just wrote down a string on my computer specifying a number whose definition is that it cannot be described by any string.

Why is this not paradox? The problem is that the set $X$, defined by "the numbers that cannot be defined by a string on my computer" is just not well-defined. To define $X$, you need to specify in advance a set of valid strings, each of which represents a natural number in a formal system in which the natural numbers can be defined, like ZFC set theory. That's because no string of characters means anything unless you have a predetermined meaning assigned to it: "43^2" might mean 1849 to a mathematician or 41 to a Python programmer.

Here is an example of such a predetermined meaning: allow valid arithmetic expressions involving only the symbols 0,1,2,3,… for every natural number and addition ("+" symbol), multiplication ("*" symbol), and exponentiation ("^"). In this system "123^5123+5" is a valid string, but "two hundred" is not, even though there is another valid string "200" that represents 200.

Now, "the smallest number that cannot be represented as a string in the aforementioned system on my computer" is a meta-statement that makes sense; this string itself is not valid for representing numbers in our fixed system, and the paradox disappears.

The Fibonacci sequence is an infinite sequence of integers $f_0,f_1,f_2,\dots$ defined by the initial values $f_0 = f_1 = 1$ and the rule
$$f_{n+1} = f_n + f_{n-1}$$
In other words, to get the next term you take the sum of the two previous terms. For example, it starts off with:
$$1,1,2,3,5,8,13,21,34,55,\dots$$
You can define all sorts of recursive sequences this way and get a whole slew of interesting patterns. The Fibonacci sequence is one of the most well-known, as it is one of the simplest and has connections to the golden ratio:
$$\lim_{n\to \infty} f_n/f_{n-1} = \frac{1 + \sqrt{5}}{2}.$$
In fact, without too great an effort you could derive an exact, closed formula for $f_n$ (i.e. a formula that does not involve recursion, or calculating previous terms to get to the next one) in which appears the golden ratio.

A theme that's been running through my research lately is looking at things modulo $m$ for some integer $m$. Reduction from $\Z$ to $\Z/m$ often happens in mathematics because there is some dictionary that tells you something about an object over $\Z$ if you know something mod $m$. So let's look at the Fibonacci sequence in $\Z/5$. It goes like this:

1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1,…

Very good looking sequence if you ask me. Notice how it starts to repeat, going right back to the beginning. Of course, it has to repeat eventually, because there are only $m^2$ elements in $\Z/m\times\Z/m$. What's a little more interesting is that it goes right back to the beginning $1,1,\dots$, rather than repeating with some new pair that appears a little later.

Why is this? It is because of the recursive definition $f_{n+1} = f_n + f_{n-1}$. We could also write it $f_{n-1} = f_{n+1} – f_n$. Therefore, if two pairs are equal $(f_s,f_{s+1}) = (f_t,f_{t+1})$ with $s \gt t$ then $f_{s-1} = f_{t-1}$. Continuing backwards we see that $f_{s – t} = f_0$ and $f_{s-t+1} = f_1$. This fact was first proved by D.D. Wall of IBM.
More »

Posted by Jason Polak on 04. November 2017 · 2 comments · Categories: elementary · Tags: ,

An irrational number $r$ is called a Liouville number if for every positive integer $n$ there exists integers $p$ and $q \gt 1$ such that
$$| r – p/q | \lt 1/q^n.$$
The requirement that $q \gt 1$ is crucial because otherwise, all irrational numbers would satisfy this definition. Liouville numbers are transcendental. In an intuitive way you could think of Liouville numbers as having pretty rapidly converging rational approximations. Here is an example of a Liouville number:
$$
r = 0.1001000000000000000000000010\dots
$$
The pattern might not be apparent but it is the number between $0$ and $1$ whose decimal expansion is all zeroes except ones in the $1^1,2^2,3^3,\dots$ places. More succintly, we can write
$$
r = \sum_{k=1}^\infty 10^{-k^k}.
$$
Let us prove that it is a Liouville number. Fix an $n$ and let
$$
r_n = \sum_{k=1}^n 10^{-k^k}
$$
Then $r_n$ is a rational number and can be written as $p/q$ with $q = 10^{-n^n}$. Then:
$$|r – r_n| = |r – p/q| \lt 1.1\times 10^{-(n+1)^{n+1}} \le 10^{-n^{n+1}} = 1/q^n$$
Therefore, $r$ is a Liouville number. This proof worked so well because I made the sequences of consecutive zeros increase very rapidly in length. Here's another question:

Is the irrational number $M = \sum_{k=1}^\infty 10^{-k^2}$ a Liouville number?

If you tried the proof I just gave for this number $M$ (so-called because it is the first letter of mystery), it won't work. But that doesn't prove that $M$ is not a Liouville number. Maybe we just weren't judicious enough in our choice of $p$ and $q$. Can you show that $M$ is or is not a Liouville number? I'll leave this to the dear reader.

There are many of Liouville numbers in the sense of cardinality: the preceding proof works if you replace the $1$s with any nonzero numbers (you can replace some of them by zero too, but you can't just replace all of them by zero). So we see the Liouville numbers have cardinality of the continuum. It's also pretty easy to see that the set of Liouville numbers is dense.

On the other hand, Liouville numbers form a set of measure zero. Therefore, there are plenty of transcendentals that are not Liouville numbers. Can you write down a specific transcendental number that is not Liouville?

Posted by Jason Polak on 03. October 2017 · Write a comment · Categories: elementary · Tags: , ,

Let $F$ be a finite field. Did you know that given any function $\varphi:F\to F$, there exists a polynomial $p\in F[x]$ such that $\varphi(a) = p(a)$ for all $a\in F$? It's not hard to produce such the required polynomial:
$$ p(x) = \sum_{a\in F} \left( \varphi(a)\prod_{b\not= a}(x – b)\prod_{b\not=a}(a-b)^{-1} \prod \right)$$
This works because every nonzero element of $F$ is not a zerodivisor.

The same cannot be said of infinite fields. If $F$ is infinite, then there are functions $\varphi:F\to F$ that cannot be represented as polynomials. That's because the cardinality of $F[x]$ is the same as that of $F$ when $F$ is infinite. However, the number of functions $F\to F$ is greater than the cardinality of $F$. Therefore, there simply aren't enough polynomials.

But, one does not have to go to infinite fields. For any prime $q$, there are functions $\Z/q^2\to \Z/q^2$ that cannot be represented as a polynomial. This is true because if $\varphi$ is a polynomial function, then $\varphi(x + q)\equiv \varphi(x)$ modulo $q$. Therefore, any of the $q^{q-2}$ functions $\varphi:\Z/q^2\to\Z/q^2$ satisfying $\varphi(0) = 0$ and $\varphi(q) = 1$ cannot be represented by polynomial.

Posted by Jason Polak on 28. June 2017 · Write a comment · Categories: elementary · Tags:

The $n$th harmonic number $h(n)$ is defined as
$$h(n) = \sum_{i=1}^n 1/i$$
The harmonic series is the associated series $\sum_{i=1}^\infty 1/i$ and it diverges. There are probably quite a few interesting ways to see this. My favourite is a simple comparison test:
$$1/1 + 1/2 + 1/3 + \cdots\\ \geq 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + \cdots
\\= 1 + 1 + 1 + \cdots$$
and the series $1 + 1 + \cdots$ is divergent. But while the harmonic series diverges, it does so rather slowly. It does so slowly enough that if you were to numerically compute the harmonic numbers (the partial sums of the harmonic series), you might be unconvinced that it actually does diverge:

  • $h(10) = 2.92896825396825\dots$
  • $h(100) = 5.18737751763962\dots$
  • $h(1000) = 7.48547086055035\dots$
  • $h(10000) = 9.78760603604438\dots$
  • $h(100000) = 12.0901461298634\dots$
  • $h(1000000) = 14.3927267228657\dots$

These numbers were computed by actually summing $1 + 1/2 + \cdots + 1/n$ and then writing out a decimal approximation to that fraction, but that takes a while. How can we at least give an approximation to this series? The first thought surely must be to compare it to the integral
$$\int_1^n 1/x dx = \log(n)$$
Where $\log(-)$ denotes the natural logarithm. A moment's consideration with Riemann sums shows that we have an inequality
$$\int_1^n 1/x dx \le h(n) \le \int_1^n 1/x dx + 1$$
So we've come up with a pretty good approximation to our harmonic series, which only gets better as $n$ gets bigger:
$$\log(n)\le h(n) \le \log(n) + 1$$
Which, incidentally is another explanation of why the harmonic series diverges. And it's much faster to compute on a simple scientific calculator. Here is an example computation: we have already said that $h(1000000) = 14.3927267228657\dots$ But $\log(1000000) = 13.8155105579643\dots$ Pretty good right?

Posted by Jason Polak on 21. March 2017 · Write a comment · Categories: elementary, exposition

Characteristic functions have magical properties. For example, consider a double summation:
$$\sum_{k=1}^M\sum_{r=1}^k a_{r,k}.$$
How do you switch the order of summation here? A geometric way to think of this is arrange the terms out and "see" that this sum must be equal to
$$\sum_{r=1}^M\sum_{k=r}^M a_{r,k}.$$
I find this unsatisfactory because the whole point of good notation is that you shouldn't have to think about what it actually means. I do think it's very important to understand what the notation means, but in doing formal manipulations it's nice not to have to do that all the time.

A superior proof that these two sums are equal would be to write
$$\sum_{k=1}^M\sum_{r=1}^k a_{r,k} = \sum_{k=1}^M\sum_{r=1}^M a_{r,k}\delta(r\leq k)$$
where $\delta(r\leq k)$ is the function of the variables $r$ and $k$ that equals one exactly when $r\leq k$ and zero otherwise. Then we can happily switch the order of summation to get
$$\sum_{r=1}^M\sum_{k=1}^M a_{r,k}\delta(r\leq k).$$
Now, it's trivial to get rid of the $\delta(r\leq k)$ function by writing
$$\sum_{r=1}^M\sum_{k=r}^M a_{r,k}.$$

Posted by Jason Polak on 19. December 2015 · Write a comment · Categories: elementary

Let $G$ be a group. Define $\varphi:G\to G$ by $\varphi(x) = x^2$. When is $\varphi$ a homomorphism? Clearly, $\varphi$ is a homomorphism whenever $G$ is abelian. Conversely, if $\varphi$ is a homomorphism then for any $x,y\in G$, we get $xyxy = \varphi(xy) = \varphi(x)\varphi(y) = x^2y^2$.

So, $xyxy = xxyy$. Canceling the $x$ from the left and the $y$ from the right gives $yx = xy$. Hence, $G$ is abelian!

One might wonder about higher power maps. What about $\varphi(x) = x^3$. Again, $\varphi$ is a homomorphism if $G$ is abelian. What about the converse? We claim that the converse holds if $\varphi$ is injective.
More »

Consider the good old Pascal's triangle:

pascal

Except for the first row, take the alternating sum of the entries. So for the second row we have $ 1 – 1 = 0$. For the third row we have $ 1 – 3 + 3 – 1 = 0$. For the fourth row we have $ 1 -4 + 6 – 4 + 1 = 0$, etc. So it seems that we have the following for $ n > 0$:

$ \sum_{i=0}^n (-1)^n\binom{n}{i} = 0$

One can use the binomial theorem to prove this. In the process of reviewing some material on regular sequences, I came up with a slightly different proof that could be the most pretentious and ridiculous proof of this fact. (However, even more ridiculous proofs using heavy machinery would be welcome in the comments.) The reader may wish to consult the previous post describing the Koszul resolution before reading onwards.
More »