### Research in Algebraic Combinatorics

I have a number of projects accessible to undergraduate students in Combinatorics, Algebra and Graph Theory. These projects can lead to a senior thesis for honors or high honors. The ideal student should have taken math 24 and preferably (although not required) Math 28, 31 (71), 38 and have some programming skills. For more details schedule an appointment.

### Enumerative Combinatorics: Pattern-Avoiding Permutations

A permutation is an ordering of the integers from 1 through n. We say that a permutation P contains another permutation Q if P has a subsequence of entries in the same relative order as Q. For example, 51423 is a permutation of length 5, and it contains the permutation 321 because the entries 5, 4, 2 are in the same relative order as 321.

The study of sets of permutations that avoid particular patterns has exploded in popularity in the last two decades. There are a number of interesting problems that are accessible to undergraduate students. I'll provide some details about two particular topics.

1) Let B be a set of permutations. The collection of permutations that avoid (do not contain) every permutation in B is called a permutation class, and is denoted Av(B). One permutation class in particular, Av({4231}), has stumped combinatorialists for many years. It is often of interest to find a formula for the number of permutations of length n in a given class, and for the permutation class Av({4231}) no such formula has been found. This project will attempt to shed some light on the enumeration of this permutation class by considering a restricted subset: the 4231-avoiding involutions.

2) When two different permutation classes have the same number of permutations of each length, they are called Wilf-equivalent. It has been conjectured that the permutation classes Av({2413}) and Av({2143,415263}) are Wilf-equivalent; this would be the smallest example of what is called unbalanced Wilf-equivalence. The goal of this project is to find a bijection between these two permutation classes.

Interested students should have some combinatorics experience (e.g., Math 28). The first project will benefit from programming experience, but this is not a requirement for the second project. Please contact me if you're interested!

### Explicit methods in number theory

Classical unsolved problems often serve as the genesis for the formulation of a rich and unified mathematical fabric. Diophantus of Alexandria first sought solutions to algebraic equations in integers almost two thousand years ago. For instance, he stated that if a two numbers can be written as the sum of squares, then their product is also a sum of two squares: since 5=2^2+1^2 and 13=3^2+2^2, then also 13*5=65 can be written as the sum of two squares, indeed 65=8^2+1^2. Equations in which only integer solutions are sought are now called Diophantine equations in his honor.

Diophantine equations may seem perfectly innocuous, but in fact within them can be found the deep and wonderously complex universe of number theory. Pierre de Fermat, a seventeenth century French lawyer and mathematician, famously wrote in his copy of Diophantus’ treatise “Arithmetica” that “it is impossible to separate a power higher than two into two like powers”, i.e., if n>2 then the equation x^n+y^n=z^n has no solution in integers x,y,z>= 1; provocatively, that he had “discovered a truly marvelous proof of this, which this margin is too narrow to contain.” This deceptively simple mathematical statement known as “Fermat’s last ‘theorem’” remained without proof until the pioneering work of Andrew Wiles, who in 1995 (building on the work of many others) used the full machinery of modern algebra to exhibit a complete proof. Over 300 years, attempts to prove there are no solutions to this innocent equation gave birth to some of the great riches of modern number theory.

Even before the work of Wiles, mathematicians recognized that geometric properties often govern the behavior of arithmetic objects. For example, Diophantus may have asked if there is a cube which is one more than a square, i.e., is there a solution in integers x,y to the equation E : x^3-y^2=1? This equation describes a curve in the plane called an elliptic curve, and a property of elliptic curves known as modularity was the central point in Wiles’s proof. One sees visibly the solution (x,y)=(1,0) to the equation—but are there any others? What happens if 1 is replaced by 2 or another number?

Computational tools provide a means to test conjectures and can sometimes furnish partial solutions; for example, one can check in a fraction of a second on a desktop computer that there is no integral point on E other than (1,0) with the coordinates x,y at most a million. Although this experiment does not furnish a proof, it is strongly suggestive. (Indeed, one can prove there are no other solutions following an argument of Leonhard Euler.) At the same time, theoretical advances fuel dramatic improvements in computation, allowing us to probe further into the Diophantine realm.

My research falls into this area of computational arithmetic geometry: I am concerned with algorithmic aspects of the problem of finding rational and integral solutions to polynomial equations, and I investigate the arithmetic of moduli spaces and elliptic curves. My work blends number theory with the explicit methods in algebra, analysis, and geometry in the exciting context of modern computation. This research is primarily theoretical, but it has potential applications in the areas of cryptography and coding theory. The foundation of modern cryptography relies upon the apparent difficulty of certain computational problems in number theory, in particular, the factorization of integers (in RSA) or the discrete logarithm problem (in elliptic curve cryptography).

I have several problems in the area of computational and explicit methods in number theory suitable for experimentation and possible resolution by motivated students. These problems can be tailored to the student based on interests, background, and personality, so there is little need to present the details here; but they all will feature a explicit mathematical approach and, very likely, some computational aspects. Mathematical maturity and curiosity is essential; some background (at the level of MATH 71) is desirable.

[Past projects]