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.
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, nobody has succeeded in giving a formula that always produces prime numbers, and 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
naturals (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 pick two and add them together,
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, l, 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=424
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.
