# Homework Help: Lattice discrete Fourier transforms

1. May 12, 2010

### Niles

1. The problem statement, all variables and given/known data
Hi

Say I have a 5x5 lattice, where each entry (or we can call it site) contains the number 1. Now, on the lattice we have a function g(R), which is equal to the number on the site. In this case g(R)=1 for all sites (here R is a vector from the point (3,3), which denotes the site we are talking about).

Now I wish to Fourier transform the function g, and I use the lattice discrete FT

$$f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R})$$

where k is a vector. Now, since each site contains the number 1, the system is homogeneous, and from the inverse Fourier transform,

$$g(\mathbf R) = \sum_{\mathbf k} e^{-i\mathbf k\mathbf R} f(\mathbf k),$$

we see that only the k=0-term can survive, since g(R) is constant. But by performing the sum

$$f(\mathbf{k}) = \sum_{\mathbf{R} } e^{i \mathbf{k} \cdot \mathbf{R} } g(\mathbf{R}),$$

it is quite obvious that all terms are there, i.e. it is not only the k=0 term that survives. That is a paradox I cannot explain. Can you guys shed some light on this?

Best,
Niles.

Last edited: May 12, 2010
2. May 12, 2010

### jbunniii

$$e^{-ik\cdot R}$$

it should be

$$e^{-2\pi i k \cdot R / N}$$

where in your case $N = 5$.

Then for $k \neq 0$ you will be summing evenly spaced samples around the unit circle, so the result will be zero.

Last edited: May 12, 2010
3. May 12, 2010

### jbunniii

P.S. Since your function is constant, the 2d DFT is equivalent to two iterated 1d DFT's. If I write $k = (k_1, k_2)$ and $R = (R_1, R_2)$, then

$$f(k) = \sum_R e^{2\pi i (k_1 R_1 + k_2 R_2) / N} = \sum_{R_1} e^{2\pi i k_1 R_1 / N} \sum_{R_2} e^{2\pi i k_2 R_2 / N}$$

4. May 12, 2010

### Niles

Thanks for helping. I just tried doing it again (with the correct factor in the exponential) for a 3x3 system, but still other terms show up (I tried writing it up manually).

5. May 13, 2010

### Niles

I'm sorry to bump the thread, but it is extremely important that this issue gets solved (I potentially have to redo 6 months of course work), and I am all out of good ideas.

Last edited: May 13, 2010
6. May 13, 2010

### jbunniii

I'm not sure what is going wrong for you. Maybe I am misinterpreting what you want to do. I wrote the following segment of Matlab code (actually Octave, but it should work for Matlab as well) to calculate your sum:

Code (Text):

fid = fopen('out.txt','w');

for a = -2:2
for b = -2:2
k = [a b];
f_k = 0;
for m = -2:2
for n = -2:2
r = [m n];
f_k = f_k + exp(i*2*pi * (k * r') / 5);
end
end
fprintf(fid, 'f([%d %d]) = %f + i*%f\n', a, b, real(f_k), imag(f_k));
end
end

fclose(fid);

Here is the result I got:

f([-2 -2]) = 0.000000 + i*0.000000
f([-2 -1]) = -0.000000 + i*0.000000
f([-2 0]) = -0.000000 + i*0.000000
f([-2 1]) = -0.000000 + i*-0.000000
f([-2 2]) = 0.000000 + i*0.000000
f([-1 -2]) = -0.000000 + i*0.000000
f([-1 -1]) = -0.000000 + i*0.000000
f([-1 0]) = 0.000000 + i*-0.000000
f([-1 1]) = -0.000000 + i*-0.000000
f([-1 2]) = 0.000000 + i*0.000000
f([0 -2]) = -0.000000 + i*0.000000
f([0 -1]) = 0.000000 + i*0.000000
f([0 0]) = 25.000000 + i*0.000000
f([0 1]) = 0.000000 + i*0.000000
f([0 2]) = -0.000000 + i*0.000000
f([1 -2]) = 0.000000 + i*0.000000
f([1 -1]) = -0.000000 + i*0.000000
f([1 0]) = 0.000000 + i*0.000000
f([1 1]) = -0.000000 + i*-0.000000
f([1 2]) = -0.000000 + i*0.000000
f([2 -2]) = 0.000000 + i*0.000000
f([2 -1]) = -0.000000 + i*0.000000
f([2 0]) = -0.000000 + i*0.000000
f([2 1]) = -0.000000 + i*0.000000
f([2 2]) = 0.000000 + i*0.000000

7. May 13, 2010

### Niles

No no, you got it. What I want to do is to find f(k). But you change the value of the k-vector? Why is it that you do that, instead of leaving it just as (kx,ky)?

8. May 13, 2010

### Niles

Wait, ignore my post #7. I will try out your example, and return when I get a result.

9. May 13, 2010

### Niles

Ok, now I get the same table as you. But the problem comes when we choose e.g. k=(0, 1.5)T - there f(k) blows up (I get f(k)=6.18 in that case).

10. May 13, 2010

### jbunniii

Yes, if you look at points that do not have integer coordinates, you will not get zero. In fact, if you evaluate f at all points (instead of just integers), you will obtain a 2-dimensional "sinc" function.

The reason for this is that you only use finitely many terms in the sum. You are in effect calculating the Fourier transform of a 2-dimensional "rectangle" function.

If you use more terms, you will more closely approximate an "impulse."

See here for a visualization: