Below, I describe my research accomplishments since 1999, those of students working directly with me as Ph.D. advisees, and my current research goals and directions. These have been loosely organized into areas, although there is often overlap.

Watermarking.
This is an area of enormously growing importance and yet one that relies on ad hoc methods. Unlike coding theory and cryptography, which now apply well-developed mathematical solutions, there is no mathematical foundation for watermarking. I have recently proposed one such involving metric spaces, in analogy to algebraic coding theory, with parameters that measure how good the watermarking scheme is. This allows discovery of better, practical schemes, for instance by using the E8 lattice instead of a rectangular lattice in the Chen-Wornell scheme. I intend to work with engineers on implementation of these new schemes and with computer scientists on picking the metric that best represents proximity in audio or video.

Codes.
Quadratic residue (QR) codes have relatively small minimum distances but these are hard to find. In one paper, using the computer algebra system MAGMA, I computed the minimum distance of the shortest binary QR code for which this was unknown. My student, Doug Kuhlman, used a similar method to do the same thing in the ternary case. Since then, I have developed general methods for handling cyclic codes. My paper bounding their minimum distances by using algebraic geometry, goes beyond the usual BCH, Hartmann-Tzeng, Roos, and shift bounds, to work with any given defining set. It reduces the problem to questions on rational points on certain projective varieties. These are solved using tools from class field theory and arithmetical algebraic geometry. With Gary McGuire I am now reproving and possibly extending results of his and Richard Wilson in characteristic 2 cases. My paper appeared in the Proceedings of WCC 2001 and will also be in Electronic Notes in Discrete Math.

QR codes can be identified as (left) ideals within group algebras of dihedral groups. Berman conducted a thorough study of minimum distances of ideals in group algebras of abelian groups, but little more has been done. With my student, Mona Musa, I am extending Berman's study to the dihedral case.

Low density parity check (LDPC) codes are proving to be amongst the best codes around (in that they approach capacity). Michael Tanner and others have suggested that there should be nice mathematical constructions of the best LDPC codes. One approach is via bipartite graphs of large girth. Examples can be constructed using Ramanujan graphs, the simplest of which arise from a method of Margulis. This was exploited by Rosenthal-Vontobel and Lafferty-Rockmore to construct LDPC codes. There are other ways to make Ramanujan graphs, such as via the theory of quaternion algebras. A student, Alison Champion, and I are constructing LDPC codes this way, taking advantage of very new MAGMA software for these computations.

Cryptography.
My student, Mark Bauer, solved one of the five fundamental problems in hyperelliptic curve cryptography, as listed by Neal Koblitz in his new book ``Algebraic aspects of cryptography''. Namely, Bauer showed how to extend the Adleman-deMarrais-Huang attack for high genus curves over odd prime fields, to any finite field, including the important but tricky binary case.

His result was not published since Enge answered the same problem (but almost a year after Bauer) and the editors preferred Enge's solution. Bauer has since written a large paper giving an explicit algorithm for adding points in the Jacobian of a cubic superelliptic curve, allowing implementation of cubic superelliptic curve cryptosystems.

The question of how often reductions mod p of a given elliptic curve over Q have order divisible by a large prime (nonsmooth) is of importance to cryptography and was considered by Koblitz using Galois representations. My student, Kuhlman, investigated the same question for reductions mod irreducible polynomials of a given elliptic curve over GF(p)(t), one advantgea being that one can arrange always to get characteristic 2 curves. In a separate paper, he used 4-dimensional Galois representations to see how often the Jacobian of a genus 2 curve has nonsmooth reductions, again for cryptographic applications.

My team of cryptography Ph.D. advisees and Research Assistants are planning various endeavors, including building a replica German Enigma machine and a MOSIS chip purpose-built for hyperelliptic curve cryptography. Both efforts should lead to papers. Richard Blahut and I have a draft of a book on cryptography, based on a course we team-taught twice.

Other Interdisciplinary.
Over twenty years ago, John Makhoul made the basic conjecture that the maximum amplitude of the response of a causal all-pass signal of order p should occur in the first 2p samples. This is applied in filter design. In 1999, the IEEE Signal Processing Society offered $1000 for resolution of this. I proved the first nontrivial case of this (p=2) and my paper was presented at ICASSP 2001, where I was given Honorable Mention. The paper also suggests a method for getting bounds for higher p (some counterexamples have been found for large p, leading to modifications of the original conjecture), which I am developing to submit to IEEE Transactions on Signal Processing.

I have made considerable improvements in the design of architectures for IIR filters. This is achieved by multiplying the transfer function's denominator by a polynomial D(z) so that the first few coefficients of the product are powers of 2. I have shown how to achieve this systematically with much lower degree D than previously obtained, resulting in reduced overheads. Naresh Shanbhag recommends I submit this to IEEE Transactions on Circuits and Systems and present it at ISCAS 2002.

Samit Basu, a student of Yoram Bresler, and I produced a technical report on identifiability of polynomial systems, related to a question in image reconstruction coming from Basu's work on tomography. We solved the problem by algebraic geometry. Unfortunately, Basu's new employers, GE, surprisingly blocked him from collaborating with people outside GE.

In addition to the above, I am tackling a basic conjecture of Helleseth on autocorrelation of sequences (amounting to counting points on certain varieties over finite fields), a problem from signal processing on when polynomial matrices factor into matrices with linear entries, and (with Ralf Koetter and Andy Singer) an extension involving more general sequential strategies of my work on ``The Weakest Link'' (see below) for ISIT 2002.

Number Theory.
Perhaps the most fundamental conjecture in algebraic number theory is that of Fontaine-Mazur, which characterizes those p-adic Galois representations that come from algebraic geometry (via Galois action on subquotients of etale cohomology groups with Tate twists) in terms of their restrictions to a decomposition subgroup at p being potentially semistable. Great progress has been made for representations ramified at p (most notably by Andrew Wiles) but those unramified at p remain a mystery. In this case, the Fontaine-Mazur conjecture says that they should have finite image. I have papers providing evidence for this and generalizations of it. In particular, the conjecture can be restated in terms of certain just-infinite (j.i.) Galois pro-p groups being nonlinear. The classification of j.i. pro-p groups leads then to my conjecture that these j.i. Galois groups should be branch, i.e. have certain large actions on rooted trees. This conjecture implies that of Fontaine-Mazur and is more constructive, in that it indicates what should exist. Using computer algebra, I have consequently produced evidence. Indeed, Galois actions on trees seem deserving of as much study as Galois actions on p-adic vector spaces have received, and I have initiated this theory. Hyman Bass, Lisa Carbone, and I are seeking invariants that can play the role that trace and automorphic forms have played for Galois actions on vector spaces. Richard Pink was recently independently led to consider Galois actions on trees in the function field case and we have begun to collaborate on this.

Galois pro-p groups unramified at p have been called by Wingberg the most mysterious in number theory. To remedy this situation (and provide evidence for the above conjectures), Charles Leedham-Green and I adapted O'Brien's p-group generation algorithm to compute some of these groups (or at least large quotients of them) by having MAGMA only save those that satisfy number-theoretic constraints at each stage. We successfully compute many of these groups, leading to some curious conjectures that are now being attacked by Helmut Koch, Farshid Hajir, and others. The paper explaining this new method was submitted It builds well beyond results of David Perry and me (which used class field theory instead of MAGMA). The new method has just been used by my student, Michael Bush, to answer an old question of Harold Stark concerning whether the class tower of a certain quadratic field is finite or not, with applications to root discriminant bounds. I have now been invited to take up a three-month distinguished visitorship at the U. of Sydney to pursue these methods further with the developers of MAGMA.

One possible extension of these methods would lead to a conjectural presentation of the Galois group of the maximal extension of Q unramified outside 2. A major question in number theory is whether this is even finitely generated. Ron Solomon and I are attempting to use local group theory methods from the classification of finite simple groups to transfer information about the structure of decomposition subgroups of G_Q to G_Q itself.

Two of my students worked on p-adic Galois representations. An old conjecture of Serre says that there should not exist representations of G_Q into GL(2,k) unramified outside p with nonsolvable image, if k is finite of characteristic p<11. Tate proved this for p=2 and Serre for p=3, but then nothing was accomplished for 25 years until my student, Sharon Brueggeman, proved it for p=5 under GRH. She also obtained some partial results in the p=7 case. My student, Darrin Doud, found a family of S4 extensions of Q ramified at one prime p and used this to define special S4-representations of G_Q into GL(3,p) and compute their universal deformation rings and relate this to work of Avner Ash.

I also have a draft of a book on the proof of Fermat's Last Theorem, based on a graduate course I offered twice at UIUC and a two-week workshop for graduate students led by Chris Skinner and me. Springer wishes to publish it.

Other work includes a joint paper with David Ose on a function field (i.e. Drinfeld module) analogue of Serre's conjecture and work by my student, Thomas Kuhnt, using rank 2 Drinfeld modules to produce curves over finite fields with many points but low genus (beating Niederreiter-Xing examples). Kuhnt is using the computer algebra system KANT to convert these curves into the theoretically best-known low-discrepancy sequences. Wall Street uses these sequences to value tranches, and I have arranged for Kuhnt's work to be evaluated by the financial software company, Numerix.

Mixed Number Theory/Group Theory.
Leedham-Green and I found an infinite family of finite 2-groups that do not embed with index 2 in any group generated by involutions. These cannot then be the Galois group of the 2-class tower of any quadratic field, in sharp contrast to the Cohen-Lenstra heuristics for their ideal class groups (saying that any abelian 2-group should appear as the first stage of such a tower). My survey talks on pro-p Galois groups and p-adic Galois representations appeared as an invited article in the volume ``New Horizons in Pro-p Groups''.

Group Theory.
Avinoam Mann and I independently defined a (truncated) Dirichlet series P(G,s) giving the probability of (pro)finite group G being generated by s elements. Thanks to a BSF grant, we collaborate on this. Andrea Lucchini recently disproved the analogue of Grushko-Neumann for profinite groups but without obtaining best bounds. By computing the formal power series P(G,s) for G a free product of finite groups and identifying its generalized Euler factors, I am seeking to fill this gap. In a paper, Judy Walker and I obtained some partial results towards an old conjecture of Richard Brauer, asking if there exists an infinite family of p-groups G such that k(G) (the number of conjugacy classes) < c log |G| for some constant c. Yiftach Barnea and I are collaborating on proving that the j.i. pro-p groups with nonzero Hausdorff dimension are precisely the branch ones (with applications to Galois actions on trees).

Miscellaneous.
I submitted a paper to the American Math Monthly solving the combinatorial problem of the best banking strategy in the TV program ``The Weakest Link''. Extensions of this have applications to coding theory. Joe Rotman asked if an extension of a finite field by a and b must be generated by a+kb for some k in the ground field. I obtained the first counterexamples and now my student, Bogdan Petrenko, has a systematic method for producing them, soon to be submitted.

October 12, 2001