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 01. June 2018 · Write a comment · Categories: computer-science · Tags: ,

This is a continuation of the OpenMP tutorial. Last time we wrote the following program:

It gives a proof that the number $N = 770948605618065977$ is prime by testing all the possible factors up to the integer part of the square root of $N$. To recap, this program creates two threads and tests half the possible factors on one thread, and half the possible factors on another thread. Wouldn't it be nice to have the program split the loop work up automatically instead of having to do it manually?
More »

Posted by Jason Polak on 30. May 2018 · Write a comment · Categories: computer-science · Tags: , , , ,

Today, I'll give you a simple and practical example of using OpenMP with gcc. What's OpenMP? It's a C/C++/Fortran library for writing multithreaded applications. What's that? Most computers these days have multiple cores so that multiple tasks can be done in parallel. With multiple cores, you can edit pictures and listen to music at the same time without a noticeable slowdown. The intensive editing computations and music decoding happen on separate cores. It's a little more complicated than that, but that's the basic idea.

If your computer has multiple cores, it can use them in a single program. That's where OpenMP comes in. For concreteness, let's say you want to test whether the number 770948605618065977 is prime. If you're sane you'd just use the Miller-Rabin test like we've been discussing on this blog, and be happy with a 99.99999% probability that the number is prime. However, let's say you want to prove this number prime by trying all the numbers up to the integer part of its square root, which is 878036790.

Here is a minimal C program to do this:
More »

Posted by Jason Polak on 25. May 2018 · 1 comment · Categories: math · Tags:

I'm hoping readers can take the time to answer this important poll. I am trying to determine the current educational background of my readers so I can better target future posts of this blog with a sufficient amount of detail.

What is your highest current level of mathematical education?

View Results

Loading ... Loading ...
Posted by Jason Polak on 25. May 2018 · Write a comment · Categories: life · Tags:

Over the years I have tried many systems to keep math notes: paper notebooks, offline WordPress installation, LaTeX files in folders, and random papers that get left on my desk for too long. None of these were ideal for all purposes. Here are the main drawbacks of each system:

  1. Paper notebooks are actually good for learning things. For reading material like books or papers in detail, paper notebooks are the best system for keeping myself on-track of going through every detail, line by line. However, the linear fashion of notebooks makes them hard to consult for main ideas. Additionally, they take up significant space.
  2. My offline WordPress installation consists of WordPress installed on Apache running on my laptop. I found it pretty terrible for notes. The blog format is good for presenting self-contained ideas over time but not so good for consulting old notes because it is not built for organising systematic knowledge. Note however, that I still use my offline WordPress installation to test-drive posts for this blog before they go live.
  3. Using LaTeX is the obvious solution to writing mathematical notes. And for large works, like complete books or papers, it is the best. However, for a general mathematical notebook, a bunch of random LaTeX documents are not easy to organize or search.
  4. Using random loose sheets of paper works for taking notes to help me learn. In this case, writing is just a tool for learning and not for storing information. After I just recycle them.

However, I've finally found system for taking notes that works. More »

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 13. May 2018 · Write a comment · Categories: number-theory

We've been talking about the Miller-Rabin randomized primality test, which is one of the easiest to implement and most effective tests that, given a number, will either prove it to be composite or state that it is most likely prime. As good as it is for practical applications, the Miller-Rabin test leaves something to be desired.

If you need primes for cryptographic applications, Miller-Rabin practically perfect. But what if you want to generate super large primes and state for sure that the numbers you are generating really are primes?

The Lucas test is a fast test that can prove a number prime. Here it is:

Theorem (Lucas Test). Let $a$ and $n\gt 1$ be integers. If $a^{n-1}\equiv 1\pmod{n}$ and $a^{(n-1)/q}\not\equiv 1\pmod{n}$ for every prime factor $q\mid n-1$ then $n$ is prime.

The proof is quite simple: the congruences that $a$ satisfy show that $a$ generate the multiplicative group $\mathbb{Z}/n^\times$. Therefore, $n-1\mid |\mathbb{Z}/n^\times| = \varphi(n)$. However, if $n$ were composite then $\varphi(n) \lt n-1$, which contradicts $n-1\mid\varphi(n)$. Therefore, $n$ is prime.
More »

Posted by Jason Polak on 11. May 2018 · Write a comment · Categories: number-theory · Tags:

Last time, I explained the Miller-Rabin probabilistic primality test. Let's recall it:

Theorem. Let $p$ be an odd prime and write $p-1 = 2^kq$ where $q$ is an odd number. If $a$ is relatively prime to $p$ then at least one of the following statements is true:

  1. $a^q\equiv 1\pmod{p}$, or
  2. One of $a^q,a^{2q},a^{4q},\dots,a^{2^{k-1}q}$ is congruent to $-1$ modulo $p$.

The Miller-Rabin randomized test looks for values of $a$ that don't satisfy the conclusions of this theorem. Such an $a$ is called a witness. If such an $a$ can be found, then $n$ is composite. If no such $a$ is found after a bunch of iterations, then we consider $n$ to be probably prime.

For example, a hundred iterations of Miller-Rabin selected

as a number that is most likely prime. A brute-force factor testing to make sure that this number is prime would take many times the age of the universe. That's pretty crazy! The Miller-Rabin test only takes a couple seconds, but how good is it really?

Now what about the percentage of witnesses for different numbers? Is this percentage close to 75%? In fact, although at least 75% of all possible bases are witnesses for any given composite number, often there are far more bases. In fact, only 0.6% of composite integers below 2000 have fewer than 90% of the total possible bases as witnesses. One such number is 1891 = 31*61. About 76% of possible bases are Miller-Rabin witnesses for 1891, which shows that the estimate of 75% is pretty good.

But for cryptographic applications, we're not interested in finding composite numbers. Given a randomly selected odd composite number, we can say that the probability of the Miller-Rabin test failing to find it composite after $k$ iterations is at most $4^{-k}$, which we can make very small very quickly. However, this conditional probability isn't the same thing as the conditional probability that a randomly selected odd number is composite given that $k$-iterations of Miller-Rabin thinks it is a prime!

A priori, it may be possible that the probability a number is composite given that $k$-iterations of Miller-Rabin thinks it's a prime is higher than $4^{-k}$.

But this isn't the case. Beauchemin, Brassard, Crépeau, Goutier, and Pomerance showed in a paper that this probability (that a randomly selected odd number is composite given $k$-iterations of Miller-Rabin thinks it is a prime) is also at most $4^{-k}$, assuming that the randomly selected odd numbers of sufficiently large (which thankfully is less than the typical modern-day cryptographic application).

Posted by Jason Polak on 09. May 2018 · 1 comment · Categories: advice · Tags:

Have you ever thought about what kind of job you can get after your math degree? I've compiled a list of the jobs I've seen so far in my own search. I've divided this post into two sections: academia, most of which require a PhD, and industry, which usually does not require a PhD.

Academia

The research postdoc has a light teaching load that allows you to do research. This is the typical next research academic position you'll get. Sadly, you might have to go through several of these before you can settle down.
More »

Posted by Jason Polak on 09. May 2018 · Write a comment · Categories: number-theory · Tags: , ,

Fermat's little theorem states that for a prime number $p$, any $a\in \Z/p^\times$ satisfies $a^{p-1} = 1$. If $p$ is not prime, this may not necessarily be true. For example:
$$2^{402} = 376 \in \Z/403^\times.$$
Therefore, we can conclude that 403 is not a prime number. In fact, $403 = 13\cdot 31$ Fermat's little theorem can be used as a test for compositeness this way: if you can find a number $a$ relatively prime to $p$ such that $a^{p-1} \not\equiv 1\pmod{p}$, then $p$ is actually composite.

If there exists an $a\in\{1,\dots,p-1\}$ with $a^{p-1}\not\equiv 1\pmod{p}$, then $a$ is called a Fermat witness to the compositeness of $p$. That is, it proves that $p$ is composite. Notice that we do not require $a$ to be relatively prime to $p$ in this definition of a Fermat witness: if any number $a\lt p$ exists with $a^{p-1}\not\equiv 1\pmod{p}$, then $p$ cannot be prime, because if it were, $a$ would actually be relatively prime to $p$ and this would contradict Fermat's little theorem.

Fermat's little theorem is a pretty good test for compositeness: if $p$ is some odd composite integer with at least one relatively prime Fermat witness, then at least half the numbers in the range $2,3,\dots,p-2$ will also be witnesses. Note: we are using this range because $p-1$ and $1$ aren't witnesses. Therefore, you can use Fermat's little theorem as a randomized prime-testing algorithm: randomly select elements $a$ from $\{2,\dots,p-2\}$ and check if they satisfy $a^{p-1} = 1\pmod{p}$. Therefore, if you have some large number $N$ that is composite and has at least one witness, a randomised Fermat's little theorem algorithm randomly testing $K$ different bases in $\{2,\dots,N-1\}$ will have probability of less than $1/2^K$ at failing to detect that $N$ is composite.
More »