# A question on discrete Fourier transform of some function

Let $$\sigma(n) = \sum_{d|n} d$$ and $$\tau(n) =$$ number of divisors of $$n$$.

For each $$k, 0 \le k \le n-1$$ we can look at the discrete Fourier transform of the numbers $$\sigma(\gcd(n,k))$$ given by:

$$\hat{\sigma}(k) = \sum_{l=0}^{n-1} \sigma(\gcd(n,l))\exp\left(\frac{-2 \pi i k l }{n}\right)$$

I implemented this in SAGEMATH, and it occured me that :

Conjecture: $$\hat{\sigma}(k) = n \tau(\gcd(n,k))$$

Is there any way to prove this?

Here is some sage-code which implements this:

def tau(n):
return len(divisors(n))

def FTS(n,k):
# Fourier Tranformierte von sigma(gcd(n,k))
return sum([ sigma(gcd(n,l))*exp(-2*pi*I/n*k*l ) for l in range(n)])

N = 8
for k in range(N):
print k,abs(FTS(N,k).N()),N*tau(gcd(N,k))


which gives:

0 32.0000000000000 32
1 8.00000000000000 8
2 16.0000000000000 16
3 8.00000000000000 8
4 24.0000000000000 24
5 8.00000000000000 8
6 16.0000000000000 16
7 8.00000000000000 8


Edit: From the conjecture above it follows, that, by setting $$k=0$$: $$\tau(n) = \frac{1}{n}\sum_{l=0}^{n-1} \sigma(\gcd(n,l))$$ for which I have a proof. By taking the inverse Fourier transform, and setting again $$k=0$$ we get: $$\sigma(n) = \sum_{l=0}^{n-1} \tau(\gcd(n,l))$$

• You may be interested in Ramanujan's sum which is related. – Somos May 4 '19 at 12:13
• @Somos: Thank you for pointing to Ramanujan's sum. That seems interesting! – user276611 May 4 '19 at 12:18
• Maybe number theoretic transform is related. – mathreadler May 4 '19 at 12:40

## 1 Answer

$$\hat{\sigma}(k)=\sum_{l=1}^n \sigma(gcd(l,n)) e^{-2i \pi lk/n} = \sum_{d | n}\sum_{l=1, gcd(l,n)=d}^n \sigma(d)e^{-2i \pi lk/n}$$ $$= \sum_{d | n}\sigma(d)\sum_{m=1,gcd(m,n)=1}^{n/d} e^{-2i \pi mk/(n/d)}=\sum_{d | n}(\sum_{r | d} r)(\sum_{l | \frac{n}{d}}\mu(l)\sum_{m=1}^{n/(dl)} e^{-2i \pi mk/(n/dl)})$$ This is a Dirichlet convolution of $$4$$ arithmetic functions and $$1$$ and $$\mu$$ cancel each other obtaining

$$= \sum_{r | n} r\sum_{m=1}^{n/r} e^{-2i \pi mk/(n/r)} = \sum_{r | n} r \frac{n}{r} 1_{ \frac{n}{r} | k} = n \tau(gcd(n,k))$$

• thanks @reuns. as always very good answer. – user276611 May 4 '19 at 17:40