This preprint is the algorithmic counterpart to the paper below.
This preprint studies recurrence equations (also called difference equations) of order 3. You've seen recurrences before: the Fibonacci numbers \(F_0,F_1,F_2\dots\) satisfies the recurrence relation \[F_{n+2}=F_{n+1}+F_{n}\text{ for }n\ge 0,\quad F_0=0,\quad F_1=1.\] Thus $$\begin{align*} && F_2&=F_1+F_0=1+0=1,\\ && F_3&=F_2+F_1=1+1=2,\\ && F_4&=F_3+F_2=2+1=3,\\ && F_5&=F_4+F_3=3+2=5,\\ && F_6&=F_5+F_4=5+3=8,\\ && &\;\;\vdots\\ \end{align*}$$
To understand the Fibonacci sequence, it is better to study the terms of the sequence all at once: we define the left shift operator \(\Phi\) to take a sequence \((s_0,s_1,s_2,\dots)\) to the sequence \((s_1,s_2,s_3,\dots)\). The Fibonacci sequence is then a solution to the operator \(\Phi^2-\Phi-1\), since \[\begin{align*} (\Phi^2-\Phi-1)(F_n)&=\Phi^2(F_n)-\Phi(F_n)-(F_n)\\ &=(F_{n+2})-(F_{n+1})-(F_{n})=(0). \end{align*}\]
Analogous to differential equations, the solutions of a recurrence operator within the set of sequences of complex numbers is a vector space over \(\mathbb{C}\) (the field of complex numbers). Moreover, the dimension of this vector space equals the order of the recurrence operator. Here, the order of a recurrence operator \[\Phi^n+f_{n-1}\Phi^{n-1}+\cdots+f_1\Phi+f_0,\quad f_0\neq 0\] is defined to be \(n\).
For any \(\lambda\in \mathbb{C}\), the exponential sequence \((1,\lambda,\lambda^2,\lambda^3,\dots)\) is an eigenvector for the left shift operator \(\Phi\), since \[\Phi(1,\lambda,\lambda^2,\lambda^3,\dots)=(\lambda,\lambda^2,\lambda^3,\lambda^4,\dots)=\lambda\cdot (1,\lambda,\lambda^2,\lambda^3,\dots).\] By plugging the exponential sequence into \(\Phi^2-\Phi-1=0\), we see that a basis of solutions for \(\Phi^2-\Phi-1=0\) is given by \[(\lambda_{\pm}^{n})_{n=0}^{\infty},\quad\text{where}\quad\lambda_{\pm}=\frac{1\pm\sqrt{5}}{2}.\] Since the Fibonacci sequence is also a solution of \(\Phi^2-\Phi-1=0\), we find that \[ F_n = c_-(\lambda_-)^n+c_+ (\lambda_+)^n\quad\text{for all }n\ge 0 \] and for some constants \(c_-,c_+\in \mathbb{C}\). Letting \(n=0\) and \(n=1\) and solving for \(c_\pm\) gives \(c_\pm=\pm 1/\sqrt{5}\). This gives an explicit formula for the Fibonacci sequence (called Binet's formula).
In the same way, we can fully understand the solutions to recurrence operators \[\Phi^n+f_{n-1}\Phi^{n-1}+\cdots+f_1\Phi+f_0,\quad f_0\neq 0\] where the \(f_i\) are complex numbers.
The next challenge is to understand the solutions to such recurrence operators when the \(f_i\) are rational functions in \(n\). These operators arise naturally. For instance, the factorial sequence \((n!)=(0!,1!,2!,\dots)\) satisfies the operator \(\Phi-(n+1)\).
The work in this preprint shows that when the recurrence operator is of order 3, and when the solutions of this operator always arise from combining solutions of lower order operators by \(+\), \(\times\), \(\Phi\), \(\Phi^{-1}\), and interlacing, then this operator is classified into the following three cases:
Here, interlacing means taking finitely many sequences like \((r_0,r_1,r_2,\dots)\), \((s_0,s_1,s_2,\dots)\), \((t_0,t_1,t_2,\dots)\), and forming the new sequence \[(r_0,s_0,t_0,r_1,s_1,t_1,r_2,s_2,t_2,\dots)\] which splices the individual sequences together.
This preprint uses difference Galois theory. Thus some texts for background prerequisites include:
gluethe following two papers together:
gluethat binds these two papers together is the use of representation theory applied directly to difference modules.
The cohomology part of this paper comes from my thesis work.
This paper contains my thesis work about how little we can simplify a general linear differential equation by certain simple operations.
You learned how to simplify polynomials in school. The substitution \(x=y-a/2\) completes the square in
\[x^2+ax+b\]
to give
\[y^2+(b+a^2/4).\]
While the original polynomial depends on two parameters \(a\) and \(b\), the simplified
polynomial \(y^2+c\) depends on only one parameter \(c=b+a^2/4\).
More generally, the translation \(x=y-a/n\) simplifies the general polynomial \[x^n+a_{n-1}x^{n-1}+\cdots+a_1x_1+a_0\] to a polynomial \[y^n+0\cdot y^{n-1}+b_{n-2}y^{n-2}+\cdots+b_1y_1+b_0\] which relies on the \(n-1\) parameters \(b_0,b_1,\dots,b_{n-2}\).
There's an analogue for this with differential equations.
Recall that a basic operation of calculus is measuring the slope of a function \(f(t)\) through its derivative \(f'(t)\). If \(t\) represents time, the slope \(f'(t)\) of \(f(t)\) describes how \(f(t)\) changes with time. It's no surprise then that differential equations—the equations involving these derivatives, and derivatives of derivatives, and so on—models our changing world, like how much time it takes a projectile to land, or the concentration of a chemical compound in a chemical reaction at a given time.
As it turns out, the first differential equations you often meet in a differential equations course can be simplified by an analogue of translation: the transformation \[y=\exp(-\frac{1}{n}\int f_{n-1}\,dx)\cdot z\] gets rid of the coefficient \(f_{n-1}\) in the general differential equation \[y^{(n)}+f_{n-1}y^{(n-1)}+\dots+f_{1}y'+f_{0}y=0.\]
My PhD thesis then gives an impossibility result:
this general differential equation cannot be simplified to fewer parameters by using simple transformations (the gauge transformations), whose coefficients are rational functions in the \(f_{i}^{(j)}\) and don't involve integrals. In hindsight, this is perhaps why you learn about these integrating factors
\(\exp(\int f\,dx)\) in differential equations class.
My work should remind you of another impossibility statement—the insolvability of the general quintic polynomial by radicals, proved via Galois theory. Indeed, my thesis uses a differential version of Galois theory. To additionally keep track of the number of coefficients that simplify away in our differential equations, I adapt the theory of essential dimension which already does this but for polynomials. Using both differential Galois theory and the notion of differential essential dimension allow me to prove my result.
This paper uses some undergraduate differential equations, group theory, field theory, and Galois theory. Some references include:
This is enough to read the introduction of the paper that introduced essential dimension:
Here are some graduate topics:
A talk on how two simple puzzles lead to ideas in algebraic topology.
Presented to the math club at Florida State University in 2022.
This is a presentation of my thesis work at Temple University Graduate Student Conference in Algebra, Geometry, and Topology (2020).