Stephen Lucas - Research

I have far too many research interests. Here is stuff I've worked on at some point in the last 20 years. What is listed is research areas where there is still scope for further work. Areas where I don't plan on further research are publications that don't relate to what is below.

History of Computation

Since elementary school, we have known how to add, subtract, multiply, and divide. As soon as we were able to use calculators, life got even easier. But why do we calculate the way we do, and just how does our calculator do things, especially when we move beyond simple arithmetic into roots, trigonometry, and logarithms and exponentials. And just how did we compute back before the invention of computers and electronic calculators?

The aim of this proposed text is a tour through the history of how we have computed, from the most ancient times to today. First, we will look at some of the different ways of representing numbers through the ages, including some that never really took off but have interesting features. Second, we will look at how to do addition, subtraction, multiplication, and division, first using counters, then later with positional notation and other variants. We will look at many different ways of doing basic arithmetic. For example, we will see ten (!) different ways of performing subtraction using positional notation. Third, we will look at various of the tools used through the ages to help us with calculation, from the sand table and abacus through to mechanical adding machines, then analog and digital calculators and computers. Finally, we will look at some of the ways developed to find square roots, evaluate trigonometric functions, and use logarithms and exponentials.

Along the way, this work has also produced two interesting papers: one on the history of subtraction through the ages, and another on comparing and contrasting different square root by subtraction methods.

Power Series Method

Ed Parker and Jim Sochacki came up with what we call the Power Series Method to solve ordinary differential equations. While initially written in terms of Picard iteration, the easiest to use form shows that if a system of odes is polynomial in its independent variables, then the Taylor series coefficients of the solution can be written explicitly in terms of previously known coefficients using Cauchy products. Even better, nearly all odes can be rewritten in polynomial form, and then rewritten in quadratic form which is most efficient in terms of numeric calculations. this means instead of being limjited to the order of a given Runge Kutta method, we can approximate a solution with an arbitrary order. Since the only calculations are addiiton and multiplication, the method is extremely quick. The current PSM team includes Jim Sochacki (JMU emeritus), myself, Paul Warne, and Roger Thelwell (JMU). We have recently been successful in applying PSM to six degree of freedom problems with gravity and atmosphere with Triton Inc.

There are a variety of topics being worked on at the moment by the team. I am particularly interested in:

Expository document: I have written an expository description of PSM in the form of textbook chapters. In the future this may end up being published or expanded upon.
Very high precision solutions: Since we can get solutions to arbitrary accuracy, we can make calculations in high precision arithmetic and so solve odes to any number of requested digits. Our only limitation is the size of the step, which is bound by the radius of convergence of the solution at any given point. We have verified convergence and found solutions to hundreds of digits of accuracy. This may lead to a new way of calculating integrals to high accuracy by converting them to odes. Current methods require building very high precision Gaussian quadrature, and as a result are rather slow.
A clean definition of stiffness: A system of odes is called "stiff" if an explicit ode solver requires tinier steps than you would expect. There are no really good definitions of stiffness beyond "it doesn't work well." Thanks to our approach with high level series approximations, we believe we have come up with a clean definition of stiffness. In short, the Taylor series coefficients of negative exponential functions initially grow like a 1/(x-a) singularity before eventually decaying factorially fast. A problem will thus be stiff is such a negative exponential is part of the solution. It may be negligible in the final solution, but its presence requires small steps, entering an artificial radius of convergence into the calculations. This also explains why implicit methods work; by going backwards, you are essentially approximating a positive exponential.
On the unreasonable effectiveness of Pade approximation: Paul Warne developed a version of PSM where he took the extra step of converting the Taylor series to a Pade approximation at each step. The extra computation is worth it if the Pade approximation is a substantial improvement on the polynomial approximation.
But this leads to the question: when is Pade better than Taylor, and what are the conditions on improvement. There is no really good answer in the literature, but we believe we can explain it. In short, we think we can prove that if the underlying function has a finite radius of convergence due to complex poles, then the Pade approximation will place singularities near those poles, and the radius of convergence is related to the first pole not accounted for by the denominator. This would explain why the error in many Pade approximations is basically a scaled version of the Taylor error, and why it looks like the solution works further from the origin. It also explains why Pade is no better than Taylor for analytic functions. Finally, we need to investigate the behavior due to branch cuts.
Functions that are not representable: Not every function (or system of odes) can be written in polynomial form. The classic example is sin(x)/x, and indeed we have trouble for any function of the form (f(x)-f(0))/x where f is smooth at zero. We have discovered that we can write them in polynomial form if we allow for occasional multiplication of the y' term by the independent variable. We can still find Taylor coefficients to arbitrary accuracy, but rather than an explicit solution, we need to solve a small system of linear equations.

Number Representation, Unusual Bases

While numbers are typically represented in base ten, sometimes other groupings are useful, such as bases two, eight or sixteen in computer science. However, these are not the only possibilities. This area of my research looks at other unusual ways of representing numbers. They include:

Negative Bases

Conversion to and from base 10.
Arithmetic in base -10: subtraction using ordinary carries and addition using reallocation.
Divisibility Tests. Joint work with Maxwell Cooper (JMU Honors Student)

No Zero

It is possible to represent integers in various bases without using the digit zero. Joint work with Dana Neidmann.

Fractional Bases

Jim Propp introduced the idea of base 3/2 using the digits {0,1,2} and the carry rule [+2,-3]. My contribution is showing how to do arithmetic in fractional bases, as well as identify when a set of digits represent an integer, and working on divisibility tests.

Multiple Bases

Base TwoAndThree: representing integers with digits that are correct simultaneously in bases two and three. This can be extended to other pairs of bases. Joint work with Jim Propp (UMass Amherst).
Irrational Bases: representing integers in an irrational base that still requires a finite number of digits. It turns out the digits are correct in all zeros of a polynomial associated with a given carry rule.
Greedy Irrational Bases: representing integers in an irrational base with a finite number of digits using only digits up to that base. This means digits obtained by a greedy algorithm match those obtained by a carry rule.
Palindromic Bases: there are some special cases where every natural number has a representation where the digits always read the same right to left as left to right.

Complex Bases

It is well known that Gaussian integers can be represented in base -n+i using the digits {0,1,...,n^2} (Katai & Sazabo 1976). I have shown that Eisenstein integers and Kleinian integers can also be represented in bases -n+w and -n+t. Addition, subtraction and multiplication is straightforward, but integer division continues to be a challenge. Experimentation with identifying real and complex parts continues.
In base 2+i we can represent Gaussian integers using digits {-1,1,0,-i,i}. I have shown how to convert to this version and do arithmetic. The combination of the distinctly different types of digits 1 and i makes for a fascinating interaction.
In base -1+i we can only represent half the Gaussian integers using the digits {0,1}. You can get all of them by allowing for a leading digit i.

Nearly Base Representations

Zeckendorff form represents an integer as a sum of non-consecutive Fibonacci numbers, and so has a relationship with (but not quite the same!) as base golden ratio. In the same way I have devised irrational base representations of integers, there are similar nearly base forms of numbers.
Skew Binary multiplies each the nth digit {0,1} by 2^{n+1}-1. As a result, it has a weird relationship to standard binary, It is an open question on whether arithmetic can be done in skew binary without converting to and from binary.

3D Printing & Mathematical Objects

In collaboration with Laura Taalman (JMU), I have been involved in a variety of projects where interesting mathematical objects are printed. They include:

Generalizing Y-Delta to X-Square: Many graphs are reducible to a single vertex by a combination of Y-Delta (remove a degree 3 vertex and join its adjacent vertices into a triangle, or vice versa) V-I (remove a degree 2 vertex and join its adjacent vertices) and I-dot (remove a degree one vertex) moves. The Petersen family is not redicible. We add a new move X-Square: remove a degree 4 vertex and join its adjacent vertices into a square or vice versa. Then the Petersen family is reducible, as are compkete graphs on 7 and 8 vertices. Open question: what are families of graphs that are not X-Square reducible, and are they the minors of any interesting graphs? With Laura Taalman (JMU) and Timothy Tarter (JMU student)
The Petersen Family, and Y-Delta Moves: The Petersen family of graphs are obtained by Y-Delta moves from the complete graphs with six vertices. Every intrinsically linked graph has one of the Petersen family as a minor. But, what do the linked cycles look like? We have shown how linked cycles in K6 can be expanded through the Petersen family, and how they stay linked as the number of vertices increase. With Laura Taalman (JMU), Claire Jones (JMU student) and Timothy Tarter (JMU student).
Ideal Spatial Graph Configurations: For obvious reasons, graphs in published literature are two dimensional images. But we can now easily print graphs in 3D. Our aim here was to come up with spatial representations of graphs that both highlight the properties of the graph and be aesthetically pleasing. We came up with a variety of ways to represent bipartite graphs, complete graphs, generalized Petersen graphs, and the Petersen family of graphs. With Laura Taalman (JMU)
Modelling Dynamical Systems for 3D printing: Inspired by some computer generated images, we showed how to efficiently build representations of chaotic curves that can be successfully printed. A successful approach was parameterizing the curve by arc length, then adding additional points where the angle between successive line segments was too small. With Evelyn Sander (GMU) and Laura Taalman (JMU).
Optimizing Morton's Tritangentless Knot: A closed curve in three dimensions is said to be tritangentless if there are no planes which are simultaneously tangent to three distinct points on the curve. In 1978, Freedman conjectured that any closed curve in three dimensions without tritangent planes must be unknotted. This conjecture was proved false in 1991 when both Morton and Montesinos exhibited explicit parameterizations of trefoil knots without any tritangent planes. But this means that a physical representation will roll. Some roll better than others, and we identified (and printed) knots that would roll as efficiently as possible. With Laura Taalman (JMU) and Abigail Eget (JMU student).

Analysis and π

Osculating Parabolas: a well known object in every Calculus III class is the osculating circle, the circle that is tangent to a curve and has the same curvature at that point. We introduce an osculating parabola that matches tangent,
Wallis-Type Infinite Products From the the Gamma Function: In 1873 (and expanded in 1875) when investigating Euler’s constant, Catalan developed an infinite product for √2 which contains half the terms from Wallis’ classic 1665 formula for π/2. Catalan’s result was derived from a particular combination of gamma functions, and was a byproduct of his main analysis. Here we show how that result can be generalized, and a variety of Wallis-like infinite products obtained for π (admittedly reproducing many previously known and algebraic numbers of the form p^q for natural number p and rational q. In the process we shall discover a new way of applying Gauss’ multiplication formula for gamma functions.
Monotonic series for fractions near π and its convergents: We discovered a wide variety of approaches to find monotonic series for fractions near π, showing it is not those particular rationals. With Amrik Nimbran.
Approximations to π derived from integrals with nonnegative integrands: as well as series, discovered a variety of ways to represent the difference between π and a fraction as an integral with a nonnegative integrand. My only American Mathematical Monthly publications! This has led to a huge number of interesting integrals by others, and some feel this could somehow be used to prove π is irrational.
An Euler-Maclaurin-like summation formula for Simpson’s rule: I have discovered just such a formula! It is derived using a nontraditional form of the error terms for Newton-Cotes integration formulas. The midpoint and trapezoidal rules lead to classic Euler-Maclaurin formulas.

Miscellaneous Projects

Analytic analysis of Parrondo's paradox: Parrondo's paradox is that you can combine playing a pair of losing games in such a way that you win. But many examples are only known by simulation. Here, we come up with analytic solutions via Markov chain analysis. With Volkan Bakirdan (past JMU student).
A direct proof of the prime number theorem: the prime number theorem is usually proven indirectly, showing it is equivalent to a statement involving the phi function. We have shown how to prove it directly in terms of the prime counting function. With Ken Lever (Cardiff) and Richard Martin.
Numerical solution of stochastic diﬀerential equations using the Karhunen-Loeve approximation: If we approximate the Wiener process by a continuous function (the KL approximation) then we can solve odes using traditional methods. We can quantify the accuracy of the KL approximation and use it to estimate how many realization are necessary to notice the error. Even better, we can adjust the KL approximation to match the variance exactly, where the errors are only in covariance terms. With Adam Diehl (past JMU student).
Motion down a curved surface: motion of a frictionless object on an incline is a classic modelling problem in introductory physics. However, if the surface is curved, there are no known analytic solutions. Here we show how to reform the problem into an amenable system of differential equations and show some interesting solutions. Along the way we deal with ill-posed systems where there are multiple possible solutions. With Jim Sochacki (JMU emeritus)
Boolean and k-potent Gröbner Bases: A problem with calculating the Gröbner basis of a system of polynomial equations is potential growth in both the size of coefficients, and the order of intermediate polynomial orders. Past work by Beth Arnold limited coefficient size using modular arithmetic approaches. Here, we look at limiting the order of polynomials in various way when the set of potential solutions is finite. With Beth Arnold (JMU)
Analysis of the game Dreidel: the classic Jewish game dreidel is often played as part of Hanukkah celebrations. Here, we simulate the outcome of a game depending on the number of players and their starting number of chips. We use both simulation and Markov Chain analysis to show who wins. With Cynthia McGrath (past JMU student)
Fitting parameters to the predator-prey equations: it turns out that finding the parameters of the predator prey equations to match a given data set is a surprisingly difficult optimization problem. We show how to reformulate the problem more efficiently.

Potential Student Projects

While there are potential undergraduate student research opportunities with much of what I currently do, here is a set of specific projects I feel could be interesting.

Fixed points in Newton's method: it turns out that when applying Newton's method to find polynomial zeros, there are certain starting points where the iteration oscillates between two values, as long as calculations are done symbolically. There are also triples of points. This project would look at the behavior of these special points, and how to generalize to finding a polynomial given the points, or increasing the period of the oscillation. Going further, can we build an elliptic curve with given rational points?
Rolling solids: The convex hull of Morton's knot rolls, but it is one of many objects that will roll, including the oloid. A research project would investigate different rolling solids, as well as minimal physical knots whose convex hull is these solids. Another open question is whethere the thickness of the knot matters.
Spatial Representations of Graphs: are there interesting ways of making new spatial representations of graphs. Topics could include graphs on spheres, tori or other surfaces, book embeddings, minor-minimal families of graphs.
Randomized Sieves and the Goldbach conjecture: a classic unsolved problem is the Goldbach conjecture, that every even number greater than or equal to four can be written as the sum of two primes. It has been verified up to 4*10^{18}. Interestingly, apart from 35 numbers up to 4208, twin primes are enough! The aim of this project is to experiment with "random sieves," that choose numbers at random with a distribution similar to that of the primes (or twin primes). What can we learn?
Bounded continued fraction representations of reals and rationals: a bounded continued fraction limits the size of the partial quotients, call F(n) the set of reals represented by a continued fraction with partial quotients at most n. An existence proof shows that every real can be written as a sum of two numbers from F(4): R=F(4)+F(4). I came up with a construction for solutions for arbitrary reals. Can it be improved upon? More interestingly, experiment shows that rational numbers can be written as sums of two finite continued fractions in F(4). Is there a way to prove this, or at least find an algorithm beyond brute force to find them?
Properties of Pierce and Engel fraction representations: Pierce and Engle fractions are variants on representing arbitrary reals (or rationals) that use integer division, as do continued fractions. There isn't much known about them. What can we find?

Page updated

Google Sites

Report abuse