Consider the following recurrence relation:
$$-2a_{n,m} +a_{n-1,m}+a_{n,m-1}=0,$$
where $a_{n,m} \in \mathbb{C}.$I would like a purely combinatorial way to understand the subspace of solutions to this equation which have tempered growth. There is an obvious solution given by setting all $a_{n,m}=C$ for any constant $C,$ and I have reasons (coming from topology) to believe that these are the only solutions with tempered growth.
Now consider the similar but probably much harder recurrence relation:
$$-2a_{n,m} +a_{n-1,m}+e^{2 \pi i n \theta}a_{n,m-1}=0$$
where $\theta$ is a fixed irrational. Note that the relation now depends on $n.$ I haven't even been able to come up with a solution to this that has tempered growth. I am hoping that it also has a 1 dimensional (or at least finite dimensional) space of solutions with tempered growth.
Is there a general combinatorial method for attacking either of these recurrence relations? Is there a general way to attack any linear recurrence relation like these?
EDIT: Let me also give my "proof" (I think it is correct) that any solution to the first relation with tempered growth must be constant. Consider the 2 dimensional torus thought of as $S^1\times S^1$, where $S^1$ is the unit circle. Now consider the function $z_1+z_2-2,$ thought of as a (finite) Fourier series. This has only 1 zero, at $(1,1).$
Now consider distributions $D$ on the torus, also thought of as Fourier series $D=\sum_\mathbb{Z^2} a_{n,m}z_1^nz_2^m$ where the $a_{n,m}$ now have only tempered growth. The first recurrence above is exactly the condition that $(z_1,+z_2 -2)D=0$ as a distribution. Since $z_1+z_2-2$ has only a single zero, the only solution with tempered growth should be a multiple of the Dirac distribution which is given by $a_{n,m}=1.$ I want a combinatorial proof or understanding of this phenomenon, since the second relation does not have this kind of topological interpretation. Ideally I would like to prove that the vector space of solutions to the second relation is also dimension 1, or is at least in some way related to the first relation.
2nd EDIT: WillSawin's answer shows that my initial proof is wrong. The space of tempered growth solutions to the first recurrence relation should be spanned (as a vector space) by the delta function and some linear combinations of its partial derivatives. Does the second recurrence have the same property? I.e. is there one "basic solution" $B$ to the second recurrence such that all other solutions can be expressed as linear combinations of the formal derivatives of $B?$
Best Answer
Polynomial growth is tempered growth, right?
I think you're failing to consider Dirac delta deriviative distributions, like the one that sends a smooth function $f(x)$ to $\frac{df}{dx} (0)$. Their Fourier series will be polynomials, like the ones that satisfy your recurrence:
$a_{n,m}=n-m$
$a_{n,m}=(n-m)^2 + (n+m)$
$a_{n,m}= (n-m)^3 + 3( n^2-m^2)$
etc.
Because the operation $a_{n,m} \to 2a_{n,m} - a_{n-1,m} - a_{n,m-1}$ sends polynomials of degree $\leq d$ to polynomials of degree $\leq d-1$, its kernel among the polynomials of degree $\leq d$ must be at least the dimension of the space of polynomials of degree $\leq d$ minus the dimension of the space of polynomials of degree $\leq d-1$, or $d+1$. Moreover, it is clear that the leading term of anything in the kernel must have the form $k (n-m)^d$. This gives a basis for the polynomial solutions.
I'm pretty sure one can show any solution to the second equation with $\theta\neq 0$ must have exponential growth, and explicitly find how large the exponential growth can be. First reparameterize:
\[a_{n,m} = \frac{ a_{n-1,m-1}+a_{n,m-1} e^{2 \pi i n \theta} }{2}\]Now we can think of this as the dynamics of an operator from functions on $\mathbb Z$ to functions on $\mathbb Z$:
\[Ta_{n} = \frac{ a_{n-1}+a_{n} e^{2 \pi i n \theta} }{2}\]Consider the Hilbert space of functions $a_n$ that satisfy $\sum_n |a_n|^2 e^{ - 2\alpha |n|} <\infty$. $T$ is a bounded operator on this Hilbert space. Let $\rho$ be its spectral radius. Since $\rho= \lim\sup_k |T^k|^{1/k}$ We have:
\[ \lim\sup_k \left(\sum_n ||a_{n,m-k}||^2 e^{ - 2\alpha |n|} \right)^{1/k} \geq 1/\rho\]so $a_{n,m}$ has exponential growth of at least $e^{\alpha |n|}$ or $\rho^{-|m|}$ in some direction. We will show that for $\alpha$ sufficiently small, $\rho<1$, so there is always exponential growth.
Suppose $\lambda$ is in the spectrum. Then $T- \lambda$ is not invertible in the Hilbert space. But we can explicitly write an inverse:
\[ ((T-\lambda)^{-1} a )n = \sum_{m=n}^\infty a_m \prod_{k=n}^m \frac{1}{2\lambda - e^{2 \pi i n \theta}} \]$\prod_{k=n}^m \frac{1}{2\lambda - e^{2 \pi i n \theta}}$ decreases rapidly. It's bounded by a multiple of $e^{-(m-n)\int_0^{1} \ln |2 \lambda - e^{2\pi i x}|dx} $ . Since $\ln | \cdot | $ is harmonic, this is just $e^{-\ln |2\lambda|}=1/2\lambda$. As long a $\alpha < \ln |2 \lambda|$, this inverse is a bounded operator, so $\lambda$ is not in the spectrum. Thus $\rho \leq e^{\alpha}/2$.
So it either has growth of at least $e^{\alpha |n|}$ or $e^{(\ln 2 - \alpha)|m|}$.
We can easily show that this is in fact exactly the spectral radius by finding an eigenvalue with $\alpha > 2 \ln |\lambda|$. By continuing the product in the opposite direction we get an eigenvalue, and by the same estimate the growth rate is less than $e^{\alpha |n|}$. Thus, there are solutions with exponential growth.
One can do a similar argument for $\theta$ a rational number, using a finite sum instead of an integral. This will give a slightly different spectral radius that is still less than $1$ for $\alpha$ small enough.