# Linear Recurrence Relations in 2 Variables with Variable Coefficients

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?$

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.

• Thanks! These solutions correspond to the fact that the partial derivatives agree at $(1,1).$ – mkreisel Apr 6 '13 at 21:28
• How does your first step work? The original recurrence gives $$a_{n,m}=\frac{a_{n-1,m}+a_{n,m-1}e^{2\pi i n\theta}}{2}$$ but you've written $$a_{n,m}=\frac{a_{n-1,m-1}+a_{n,m-1}e^{2\pi i n\theta}}{2}.$$ – mkreisel Apr 7 '13 at 14:52
• Replace $m$ with $m+n$. – Will Sawin Apr 7 '13 at 16:38
• Sorry if I'm being obtuse, but I'm still having trouble understanding your solution. I now understand how the operator $T$ helps; if $a_{n,m}$ satisfies the recurrence relation I can take $b_n=a_{n,-n}$ to be my "initial data" and then applying $T$ yields the values $Tb_n=a_{n,1-n}.$ So understanding the dynamics of $T$ tells me about the growth of the sequence as we move up and to the right in the $\mathbb{Z}^2$ lattice. However it cannot tell us about the lower left portion of the grid... – mkreisel Apr 8 '13 at 17:22
• My answer certainly isn't the clearest. We have the identity $T^n a_{-n,m}=a_{0,m}$, which implies the inequality $|| a_{0,m}|| \leq ||T^n|| ||a_{-n,m}||$, so $||a_{-n,m}|| \geq ||a_{0,m}|| /||T^n||$. Thus if $1/||T^n||$ grows exponentialy, $a_{n,m}$ does as well. – Will Sawin Apr 8 '13 at 18:11

I don't think constant is the only tempered growth solution to your 2d recurrence. Essentially the recurrence needs a 1-dimensional subspace in $\mathbb{Z}^2$ of boundary conditions. Then your recurrence is saying the value at any point $(x,y)$ is the average of values at $(x-1,y)$ and $(x,y-1)$, which has the effect of smoothing things out as we move to the upper right corner of the 2d lattice.

For instance, take the subspace $S = \{(i,-i): i \in \mathbb{Z}\}$. Then you can prescribe any values on points in $S$ and get a consistent solution first on the part of the integer lattice to the up-left of $S$. If you choose the values on $S$ to be say bounded, then the solution on the upper left side of $S$ will also be bounded, hence certainly "tempered". Now to extend this solution below and to the left of $S$, just assign $0$ to all points in $T =\{(i,i): i < 0\}$ and all the other points in the bottom left corner of the lattice are uniquely determined. Again it's easy to see they are all bounded.

Your second recurrence can be treated in the same way. One trivial solution is to assign all points constant at $0$. On the other hand I imagine it can be quite interesting to consider 2d recurrences where the coefficients do not add up to 0 (or cannot be arranged on the right and left of the equality so that the moduli of two sides add up to the same number) hence can exhibit exponential growth. But maybe that case can be reduced to 1d recurrence.

• I do not think this is quite right. I agree that if you specify $S=\{(-i,i)\}_{i \in \mathbb{Z}}$ then the region above and to the right of $S$ is determined and bounded. However your extension to the lower left does not make sense to me. It is not clear to me how specifying $T=\{(i,i)_{i<0}\}$ determines the rest of the grid. So instead consider this example. Let $a_{n,m} = 1$ on $S$, and thus $a_{n,m}=1$ whenever $n+m>1$ as well. Now let $a_{0,m}=0$ for all $m<0,$ similar to what you have described. This fully determines the grid as we can now work down the lower diagonals one at a time... – mkreisel Apr 6 '13 at 18:57
• However, in this case we have $a_{-n,0} = 2^n,$ so this solution clearly cannot be tempered since it is growing exponentially in $n$ in this direction. To see that $a_{-n,0}=2^n,$ note that because we have placed zeros on the half-column $a_{0,-m},$ the strict lower left quadrant $m,n<0$ will be entirely zero, and in particular the half-row $a_{m,-1} = 0$ for $m<1.$ Thus since we placed a 1 at $a_{0,0},$ we get $a_{-1,0}=2,$ and since the entire half-row is zero we get $a_{-n,0} = 2^n.$ So just specifying a bounded initial data does not mean the whole sequence remains bounded, nor tempered. – mkreisel Apr 6 '13 at 19:06
• @mkreisel: yes you are right. The lower half of the plane is the more interesting part. There is more structure to the problem than I thought. – John Jiang Apr 7 '13 at 1:03

This recurrence brings to mind the wave equation. Denote by $L$ the lattice $\newcommand{\bZ}{\mathbb{Z}}$ $L=\bZ^2$ and $t:L\to\bZ$ the "time" function

$$t(x,y)=x+y,\;\; (x,y)\in L.$$

The "initial hypersurface" $S_0$ is defined by the equation $T=0$. A point $p=(x,y)\in L$, $t(p)>0$, is uniquely determined by its time $t(p)=x+y$ and its position $u(p)=x-y$. $\newcommand{\bC}{\mathbb{C}}$

Consider a function $a:L\to\bC$ satisfying your recurrence relation. Its value at the point $(x,y)$ with time $t=(x_0,y_0)$ is only affected by its values in the region $|x-x_0|\leq t$ on initial hypersurface $S_0$.

For any $R>0$ define

$$S_0(R,t)= \lbrace (x,y)\in L;\;\;x+y=t,\;\;|x|\leq R\rbrace,$$

and

$$m(R, t) :=\max_{(x,y)\in S(R, t)}|a(x,y)|.$$

$$|a(x,y|\leq \frac{1}{2}\bigl(\; |a(x-1,y)|+|a(x,y)|\;\bigr),\;\;\forall (x,y)\in R.$$

This implies immediately that

$$m(R,t) \leq m(R+1, t-1).$$

In particular, for $t>0$ we have

$$m(R,t)\leq m(R+t,0).$$

This controls the size of the "future" values of $a$, i.e., the values of $a$ in the region $t\geq 0$. If we assume that

$$m(R,0)\leq Ma^R,$$

for some $c\geq 1$, $M>0$ then we deduce that

$$M(R,t)\leq M a^{R+t},\;\;\forall t\geq 0.$$

In particular, if $a$ is bounded along $S_0$, it will stay bounded in the future. The past values seem a bit more difficult to control. I have to think more about this.

I thought more about this and I reached a conclusion: the past cannot be determined from the initial conditions at $t=0$.

Suppose that we have a function $a: \bZ\to \bC$ satisfying your recurrence conditions and such that, at $t=0$ is zero. What could be the values on the time slice $t=-1$?. Denote by $A$ the restriction of $a$ to the slice $t=-1$. We set $\newcommand{\ii}{\boldsymbol{i}}$

$$A_n = a(n,-n-1),\;\;n\in\bZ.$$

Set $c:=e^{\ii\theta}$. The recurrence relation implies

$$A_n +c^n A_{n-1}= 0,\forall n\in\bZ$$

so that

$$A_n = A_0 (-c)^{\ell(n)},\;\;\ell(0)=0,\;\;\ell(n+1)-\ell(n)=n,\;\;\forall n\in\bZ$$

This shows that we can generate solutions of your recurrence that are far from temperate for $t<0$. Here is how you do it.

Fix a function $f_0 :\bZ\to\bC$. This is the initial condition

$$a(x,-x)=f_0(x),\;\;\forall x\in \bZ.$$

Define $g_{-1}:\bZ\to \bC$ by requiring

$$g_{-1}(0)=0,\;\;g_{-1}(x)+cg_{-1}(x-1) = 2f_0(x),\;\;\forall x\in \bZ.$$

Pick a constant $M_1>0$ and then set

$$f_{-1}(x) = M_1 (-c)^{\ell(x)} +g_{-1}(x),\;\;\forall x\in \bZ.$$

Observe that $f_{-1}(0)= M_1+1$ and

$$f_{-1}(x)+c^xf_{-1}(x-1)=2f_0(x).$$

Proceed inductively. Suppose we have produced functions $f_{-1},\dotsc, f_{-k}:\bZ\to \bC$,

$$f_{-j}(0)= M_j+1,\;\;j=1,\dotsc, k.$$

We determine $g_{-k-1}:\bZ\to \bC$ by requiring that

$$g_{-k-1}(0)=0,\;\; g_{-k-1}(x)+c^xg_{-k-1}(x-1)= 2f_{-k}(x),\;\;\forall x\in \bZ.$$

Pick a positive constant $M_{k+1}$ and then set

$$f_{-k-1}(x) := M_{k+1}(-c)^{\ell(x)}+ g_{-k-1}(x),\;\;\forall x\in\bZ.$$

For $k>0$ we define inductively $f_k:\bZ\to \bC$

$$f_k(x)=\frac{1}{2}\bigl(\; f_{k-1}(x)+c^xf_{k-1}(x-1)\;\bigr).$$

Finally define $a:\bZ^2\to\bC$ by setting

$$a(x,y)= f_{x+y}(x),\;\;\forall (x,y)\in\bZ^2.$$

The function $a$ satisfies the recurrence relation and

$$a(0, -k) = M_k+1,\;\;\forall k\in \bZ_{>0}.$$

By choosing the sequence $M_k$ suitably, e.g. $M_k = k^{k!}$, your guaranteed a non-temperate behavior for $a$.

Remark 1. Suppose we are given a function $f_0:S_0\to\bC$, a sequence of points $p_n=(x_n,y_n)$, $n>0$, so that $t(p_n)=x_n+y_n)=-n$ and a sequence of complex numbers $C_n$, $n>0$. Then there exists a unique solution $a$ of the recurrence equation satisfying the "initial conditions"

$$a(p_n)= C_n,\;\;\forall n>0,$$

$$a(x,y)= f_0(x,y),\;\;\forall (x,y)=S_0.$$

Remark 2. To obtain estimates for the growth of this solutions in the past one needs to understand the growth of the solution of the following initial value problem. Given $f:\bZ\to \bC$ let $u:\bZ\to\bC$ be the solution of the initial value problem

$$u(x)+c^xu(x-1) = 2f(x),\;\; x\in \bZ,$$

$$u(0) =0.$$

Note that

$$u(1)= 2f(1),\;\; u(2)= -c^2 u(1) + 2f(2)=-2c^{\ell(2)} f(1)+2f(2),$$

$$u(3)= -c^3u(2)+2f(3)= 2f(3) -2c^3f(2) +2c^{\ell(3)} f(1)$$

$$= 2(-c)^{\ell(3)}\bigl(\; (-c)^{-\ell(3)} f(3)+(-c)^{-\ell(2)}f(2)+(-c)^{-\ell(1)} f(1)\;\bigr). \tag{1}$$

The pattern is now clear and one can see that

$$u(n)\leq 2\bigl( |f(1)|+ \cdots +2|f(n)|\;\bigr).$$

This is an optimal bound which is achieved. Suppose for example that

$$f(n)= (-c)^{-\ell(n)} r_n,\;\; r_n>0$$

Then

$$u(n)= 2(-c)^n (r_1+\cdots + r_n), \;\; n>0.$$

The solution with the temperate initial condition

$$a(n,-n)= (-c)^{\ell(n)} ,\;\;n\in\bZ,$$

$$a(0,-n)=0,\;\; n>0,$$

is non-temperate because $|a(1,1-t)|=2^t$, $\forall t\geq 0$.

In general is satisfies an estimate of of the type

$$a(n,n-t)\sim 2^t \frac{n^t}{t!},\;\; t>0,\;\; n>n(t).$$

Remark 3. If the "initial" condition for $a$ is the $\delta$ function concentrated at the orgin, then $a$ has exponential growth in the past.

More precisely, if $a$ satisfies the recurrence and the initial conditions

$$a(x,-x)=0,\;\;\forall x\in\bZ\setminus 0,\;\;a(0,0)=1,$$

$$a(0,-t)=0,\;\;\forall t<0,$$

then $$|a(1,1-t)|=2^t.$$

• As I noted in the comment above, specifying the $S_0$ plus the values of $a(0,n), n<0$ will completely determine the grid for either relation. Clearly if we make either of these choices in a way that does not have tempered growth then the solution they determine will not have tempered growth. I think the solutions you describe above were essentially chosen, as I described, not to have tempered growth. What is more interesting to me is whether choosing bounded or temperate growth initial data leads to a bounded/temperate growth solution. – mkreisel Apr 6 '13 at 19:37
• Isn't it more like the heat equation than the wave equation? – Will Sawin Apr 6 '13 at 20:31
• It is rather strange. The future behavior is like the wave equation. If the initial condition is supported at the origin, say $a(0,0)=1$ and $a(x,-x)=0$, for $x\neq 0$, then on the slice $t=1$ there are only two points where $a\neq 0$, namely the points $a(1,0)$ and $a(0,-1)$. The heat propagates instantaneously so that if the initial condition is Dirac concentrated at $0$ the temperature after $\epsilon$ seconds at a point $x$ is not $0$ it is $\frac{1}{\sqrt{4\pi\epsilon}} e^{-\frac{x^2}{4\epsilon}}$. – Liviu Nicolaescu Apr 6 '13 at 21:41
• @ mkreisel See the update to my answer where I construct a non-temperate solution with temperate initial data. – Liviu Nicolaescu Apr 6 '13 at 22:19