0
votes
1answer
50 views

Berlekamp Massey and DFT

I was looking into the Berlekamp Massey algortihm, for LFSR, over GF(2) wondering if there was any DFT(alternately FFT), for the above scheme. Also, is there any generalization to Fn, ie, start ...
3
votes
1answer
46 views

Lower bound on certain exponential sums and expressions related to them

Let $$G(\alpha, x) = \sum_{n\le x}e(\alpha n^2)$$ Clearly, $r_k(n)$, the number of representations of a number as the sum of $k$ squares is given by the following expression: $$r_k(n) = \int_0^1 ...
6
votes
1answer
72 views

Gowers' proof of Szemerdi's theorem

Are there any good books or other resources (expository notes) which explains Gowers' proof of Szemerdi's theorem in detail?
0
votes
0answers
13 views

Fourier transform of a quasi character on a local field

Why is the twice iterated fourier transform of a quasi-character $c$ on local field $k$, $c$ itself? That is, why is $\hat{\hat c}(\alpha) = c(\alpha)$? In general, when we apply the fourier transform ...
0
votes
0answers
12 views

When is the fourier transform of a quasi-character $\hat c(\alpha)=|\alpha|c^{-1}(\alpha)$?

This is from lemma $2.4.2$ of Tate's thesis. Let $c$ be a quasi-character on $k^{*}$, the multiplicative group of a number field completed at a non-archimedian place. Lemma 2.4.2 For $c$ in the ...
2
votes
1answer
44 views

Equidistribution of $\{\xi_n\}$ where $\xi_n = <n\frac{p}{q}>$ $p,q$ rel. prime

I'm working from Stein's An Introduction to Fourier Analysis, and there's a question (chapter 4 number 6): Let $\theta = \frac{p}{q} \in \mathbb{Q}$ where $\operatorname{gcd}(p,q) = 1$. Assume ...
6
votes
1answer
79 views

percentage of numbers starting with $2$ in $\{2^n\}$

I have once heard a professor telling (during a course on Fourier theory) that there is a way to determine the numbers starting with a $2$ in the sequence $\{2^n\colon n\in\mathbb{N}\}$. I asked him ...
4
votes
2answers
234 views

Some identities with the Riemann zeta function

Can someone either help derive or give a reference to the identities in Appendix B, page 27 of this, http://arxiv.org/pdf/1111.6290v2.pdf Here is a reproduction of Appendix B from Klebanov, Pufu, ...
9
votes
1answer
509 views

How to justify the solution of this problem?

Assume $\mathbf{x} \in \mathbb R_+^N$ with support $P=\{p_1,p_2,\cdots,p_K\}$ ($P$ is unknown). We already know that $$f_1(\mathbf{x}) = f_2(\mathbf{x}) = \cdots = f_{N-1}(\mathbf{x})$$ where ...
27
votes
0answers
856 views

Is this similarity to the Fourier transform of the von Mangoldt function real?

Mathematica knows that the logarithm of $n$ is: $$\log(n) = \lim\limits_{s \rightarrow 1} \zeta(s)\left(1 - \frac{1}{n^{(s - 1)}}\right)$$ The von Mangoldt function should then be: ...
1
vote
0answers
142 views

Fourier Analysis of Prime Counting Function

I was thinking about the following: Denote $\pi(x)$ as the prime counting function such that: $$ \pi(x) = \#\text{ of prime numbers}\leq x $$ It is well known from the prime number theorem that $$ ...
-1
votes
1answer
129 views

The maximum absolute value of DFT of window vector

Let x=[1, ⋯ ,1, 0, ⋯ ,0] be a window vector of length N, which consists of B consecutive 1s and the remaining N-B consecutive 0s. I took the N-point DFT on x and got X=[X_0, X_1, ⋯, X_(N-1)] which is ...
2
votes
0answers
74 views

A question on algorithm complexity

It is well-known that the evaluating the Discrete Fourier Transform definition directly has a complexity $O(N^{2})$ for a signal with bandwidth $N$. How to see or show that the fast Fourier transform ...
2
votes
1answer
134 views

The digit base and the NTT convolution

Suppose I'm using a number theoretic transform (NTT) in an integer field $GF(p)$. I assume that $2n$-th root of unity exists for such a $p$, and I want to compute a convolution of two $n$-length ...
6
votes
1answer
232 views

An elegant non-technical account on the work of Joseph Fourier.

It would seem difficult for a naive person to understand the beauty of work done by Fourier. So as far as I know, one can use the Fourier transforms, analysis and series to apply them for heat ...
2
votes
0answers
207 views

What are the local minima in this spectrum?

Edit 6.2.2012: The sequence to be transformed should be f = 0,1,2,3,4,5... which makes the mentioning of the von Mangoldt function less necessary. Edit 5.2.2012: I had the wrong plot of the insignal. ...
3
votes
0answers
330 views

How plot the Riemann zeta zero spectrum with the Fourier transform? [closed]

This question is closed as off-topic and duplicate of How plot the Riemann zeta zero spectrum with the Fourier transform in Mathematica? In the paper "The Riemann Hypothesis" by J. Brian Conrey ...
3
votes
0answers
196 views

The discrete Fourier transform of a Dirichlet charachter

I usually work in number theory so I am not familiar with Fourier transforms, I have read up on them and know the basics but it never seems to be in number theory language. I am trying to find the ...
15
votes
5answers
850 views

Interpretation of Poisson Summation Formula

This question arises from a Fourier transform class I took about a year back. The poisson summation formula is: $$\displaystyle \sum_{n= - \infty}^{\infty} f(n) = \displaystyle \sum_{k= - ...