I
describe my research to other mathematicians as "combinatorial
number theory". The truth is that most combinatorialists consider
it number theory and most number theorists consider it
combinatorics. More recently, I've been working on computational
number theory, which is a largely a mix of programming, calculus,
and numerical analysis.
Number theory is the study of properties of the natural
numbers 0, 1, 2, 3, .... For example, p is a prime
number if it is not the product of two smaller numbers. So, 14 is
not a prime number (14=2*7), and also 15 and 16 are not prime
numbers, but 17 is. So the first question is how many prime
numbers are there? The next question is what are they? We know
that there are infinitely many, and we even know approximately how
many there are less than x,
for any number x. To
date, we don't even know how many n make 2^n+1
a prime (we believe infinitely many) or make 2^(2^n)+1 a prime (we believe
there are only 5).
Combinatorics starts with the science of counting. Sound easy? It
starts that way, but as with everything humans touch it has grown
in difficulty to the point that progress is more art than science.
How many different Su Doku boards are there? Questions about
certain objects are more amenable to solution by counting than
others, and the study of such objects (graphs, hypergraphs,
permutations, et cetera) is also considered to be combinatorics.
Here's a favorite game: I put some points on a sheet of paper, and
connect some pairs with curves in such a way that you can go from
any point to any other point on the curves, but you can't get back
to where you started without backtracking. Now you get to label
the points with distinct nonnegative integers, and label each
curve with the difference of the labels of the points at its two
ends. If you have labeled the curves with the numbers 1, 2, ...,
each curve getting a different number and no number being skipped,
then you win. Otherwise I win. There's evidence that you can
always win (for example, you can win if I start with 16 points, no
matter how I draw the curves or how many curves I draw), but
nobody knows for sure --- yet.
Combinatorial number theory consists of questions about the
natural numbers {0, 1, 2, ...} that can be addressed with
combinatorics. My favorite example is that of Sidon sets. A Sidon
set is a set of naturals with the property that if you secretly
pick two and announce their sum, then I can take that sum and
figure out which two you picked. For example, the set {2,3,4} is
not a Sidon set, if you give the sum 6 then I couldn't deduce if
you had picked 2 and 4, or if you had picked 3 twice. The set {0,
1, 4, 6} is a Sidon set. So the question is how many elements can
be in a Sidon set if the largest element is n? Even with n=1000 the answer is not
known. The problem (and its partial solutions) have been used in
cryptography, radio frequency assignments, and in other seemingly
unrelated areas.
These problems are appealing for several reasons. A big reason is
that they are easy to state and explain. Another reason is that I
enjoy programming and some of these problems can be approached
experimentally. Another reason is that I enjoy the company of many
people who also enjoy these problems.