Kempner Colloquium Abstracts

Fall 2006

Class one Whittaker functions are special functions on Lie groups that are important in representation theory and number theory, and also appear in physics. In the case of SL(2, R), the class one Whittaker function is essentially the classical Whittaker function (or K-Bessel function). Explicit integral representations for SL(n, R) have been obtained by Stade. We will talk about a new formula for SL(n, R) (joint work with Stade) and extensions to other classical groups. We will also discuss possible applications to number theory.

Most of the rings one encounters as "basic examples" have what's known as the "Invariant Basis Number" property, namely, for every pair of positive integers m and n, if the free left R-modules _RR^(m) and _RR⁽ⁿ⁾ are isomorphic, then m=n. There are, however, large classes of naturally occurring rings that do not have this property. While at first glance such rings might seem pathological, in fact they arise quite naturally in a number of contexts (e.g. as endomorphism rings of infinite dimensional vector spaces), and possess a significant (perhaps surprising) amount of structure. We describe a class of such rings, the (now-classical) Leavitt algebras, and then describe their recently developed generalizations, the Leavitt path algebras. One of the nice aspects of this subject is that pictorial representations (using graphs) of the algebras are readily available. Indeed, many of the results in this subject depend on rather intriguing graph-theoretic concepts. In addition, there are strong connections between these algebraic structures and a class of C^*-algebras (the "Cuntz-Krieger graph C^*-algebras"), a connection which is currently the subject of great interest to both algebraists and analysts. This talk should have "something for everyone", and should be "accessible to everyone".

One day, while we were having lunch together in the mathematics common room, my colleague Victor Guillemin excitedly rushed to the blackboard to tell me that if f : R -> C is a smooth, periodic function with period 1, then the difference between the Riemann approximation

R_N(f) = (1/N) ∑^N_{m = 1} f(m/N)

A wide variety of combinatorial problems can be expressed within the framework of the Constraint Satisfaction Problem (CSP). One useful way to define a subclass of the CSP is to restrict the relations that appear in the constraints of an instance of the problem, to range over a specified set of (finitary) relations on some fixed (finite) domain. This amounts to specifying a finite general algebra A and considering all instances of the CSP where the constraints are defined by invariant relations (subalgebras of finite powers, or subpowers) of A. Thus for a given finite algebra A, we have a specific algorithmic problem, CSP(A). In a seminal paper, T. Feder and M. Y. Vardi conjectured that if the relational clone Inv(A) of all invariant relations over A is finitely generated, then CSP(A) satisfies dichotomy: the problem either admits a polynomial-time algorithm, or is NP-complete. V. Dalmau presented a polynomial time algorithm, a natural generalization of Gaussian elimination, that solves CSP(A) for finite algebras A that possess a certain type of term operation. An algebra with such an operation has only polynomially many invariant relations; and there is a persuasive heuristic argument that if CSP(A) admits an algorithm that works somewhat like Gaussian elimination, then A has polynomially many invariant relations. (We say that A has few subpowers.)

The author, with J. Berman, P. Idziak, P. Markovic, M. Valeriote and R. Willard, has investigated the class of finite algebras with few subpowers, obtaining several characterizations of these algebras that yield interesting algebraic results. Ultimately, we proved that if A has few subpowers, then CSP(A) admits a polynomial time algorithm that "works like" Gaussian elimination. The talk will describe this work, and discuss some of the ongoing efforts to resolve the Feder and Vardi conjecture.

The talk will consider a class of problems in the elementary geometry of Hilbert space that are not only of interest for themselves, but through the medium of group theory have perhaps surprising applications to the study of the distribution of rational prime numbers.

A special case of the problem of flying an airplane with stuck controls (and limited fuel) is finding the shortest curve of a given constant (nonzero) torsion between two points. (In order to make the problem interesting, we fix the osculating plane at each endpoint.) Geometric variational problems like this one, with differential constraints, can be solved using the Griffiths formalism. The Euler-Lagrange equations have an interesting connection to elasticity theory which allows them to be solved exactly. Considerations of the solutions lead to a simple class of boundary conditions which cannot be realized by smooth minimizers.

In order to understand a class of von Neumann algebras called free group factors, Dan Voiculescu developed a noncommutative probability theory for them which he called free probability. One of the major tools of free probability involves the use of a matricial microstate spaces. Roughly speaking, matricial microstate spaces are subsets of Euclidean space and thus can be studied using classical analytic techniques. I will discuss how geometric measure theory can be used to understand the structure of microstate spaces and provide nonisomorphism theorems for von Neumann algebras.

This talk should be accessible to graduate students with some knowledge of functional analysis (e.g., Hilbert spaces, operators, measure theory).

Several disparate phenomena have been characterized by permutation pattern avoidance including: computer science stack sortability, geometric information about Schubert varieties, and properties on the set of reduced words of a permutation. In this talk, we will introduce permutation patterns and survey some recent enumerative results. Then, we discuss generalizations of pattern avoidance for other Coxeter groups, and introduce embedded factor patterns. Finally, we will describe recent work which uses these embedded factor patterns to characterize when the Kazhdan-Lusztig polynomials (that arise in representation theory and geometry of Schubert varieties) have a simple combinatorial formula via a framework of Deodhar.

This is joint work with Sara Billey.

Over the last twenty-five years, a number of ingenious schemes have been developed for ensuring the security of communication. Several of these, such as RSA, rely on the presumed difficulty of the integer factoring problem. In order to use such a scheme it is first necessary to find two large prime numbers (primes) whose product is made public. The inability of an eavesdropper to determine these two primes, given their product, is what makes the system safe. This, of course, leads us to the question of how to identify the large primes that would be used in such a scheme. The problem of establishing that a given integer is a prime is called the problem of primality proving. The usual way we learn to do this is to trial divide the number by all primes less than its square root; if no such prime divides the original number, than it must be a prime number. Unfortunately, this technique is hopelessly impractical for the numbers that need to be used in the RSA cryptosystem.

The recent proof by Agrawal, Kayal and Saxena that primality proving of a given integer N can be done efficiently (in deterministic polynomial time) has stimulated a lot of research into just how efficiently we could expect to do this. According to a conjecture on the growth rate of certain numbers called pseudosquares, this time complexity would be O((log N)^{3 + ε}), a result that some consider to be best possible. Briefly put, a pseudosquare is an integer that acts in some respects like a perfect integer square, but is not such a square. These numbers were first considered by Kraïtchik, who computed several of them in 1924. Since that time a number of investigators have added to Kraïtchik's table.

The process of finding these numbers has always involved the use of a device called a number sieve. This machine detects the pseudosquares simply by searching through all integers up to a certain, pre-selected bound. While this approach may sound naive, it is in fact possible through a judicious exploitation of parallelism to make these devices execute at a very rapid rate; indeed, the use of these machines is the fastest method known for finding pseudosquares. In this talk I will discuss some of these machines, the oldest dating back to 1912. I will also give a brief description of a recently completed number sieve (CASSIE) constructed at the University of Calgary by Kjell Wooding. With this new device, which for the pseudosquare problem can be made to execute up to 1000 times faster than the fastest previous number sieve, we were able to find 12 new pseudosquares. These numbers also conform to the conjectured growth rate, providing more evidence for the widely believed complexity of the problem of primality testing. We are also able to make use of these results to find the fastest known primality proving algorithm for numbers of 100 bits. This is very useful for digital signature verification.

In this talk we will describe results and discuss problems of interest in different areas of primality testing:

• Primality Tests for special family of numbers.
• Probabilistic Primality Tests.
• ERH Conditional Primality Tests.
• General Primality Tests.