Question

My questions . Please, help

Answer 1

Questions on the papers.

Answer 2

those are your questions?

Answer 3

breaking the sum is done in much the same way I did before, using the fact that the summand is periodic with respect to \(N\): $$e^{2\pi i(qN+r)^2/N}=e^{2\pi i(q^2N^2+2qrN+r^2)}=e^{2\pi i(qN+2qr)}\cdot e^{2\pi ir^2/N}=e^{2\pi ir^2/N}$$

Answer 4

so since the summand is periodic with \(N\), when we break it into individual sums for \(k\) between \(1,N\), then \(N+1,2N\), then \(2N+1\) to \(3N\), up to \(q(N-1)+1\) to \(qN\), and lastly a sum from \(qN+1\) to \(qN+r\) we see: $$\sum_{k=1}^Ne^{2\pi ik^2/N}=\sum_{k=N+1}^{2N} e^{2\pi ik^2/N}=\dots=\sum_{k=q(N-1)+1}^{qN} e^{2\pi ik^2/N}$$ so the sums on the \(q\) intervals above are all equal, so their total sum is just \(q\) times any one of the sums independently: $$\begin{align*}\sum_{k=1}^{qN+r} e^{2\pi ik^2/N}&=\underbrace{\sum_{k=1}^Ne^{2\pi ik^2/N}+\dots+\sum_{k=q(N-1)+1}^{qN} e^{2\pi ik^2/N}}_{q\text{ sums on blocks of N}}+\sum_{k=qN+1}^{qN+r}e^{2\pi ik^2/N}\\&=q\sum_{k=1}^N e^{2\pi ik^2/N}+\sum_{k=qN+1}^{qN+r} e^{2\pi ik^2/N}\end{align*}$$
now we use the periodicity to simplify the indices of the last block, rewriting instead for \(k=1\) to \(k=r\): $$\begin{align*}\sum_{k=1}^{qN+r} e^{2\pi ik^2/N}&=q\sum_{k=1}^N e^{2\pi ik^2/N}+\sum_{k=1}^r e^{2\pi ik^2/N}\end{align*}$$

Answer 5

switching to \(k=0,\dots,N-1\) from \(k=1,\dots,N\) in the first doesn't change a thing, since the summand is periodic in \(k\) with period \(N\) and thus the terms for \(k=0\) and \(k=N\) are identical: $$\underbrace{e^{2\pi i0^2/N^2}}_{\text{summand at }k=0}=e^0=1=e^{2\pi i}=\underbrace{e^{2\pi iN^2/N^2}}_{\text{summand at }k=N}$$

Answer 6

and, yes, you are correct in your expressions for \(G,O\)

Answer 7

\(n=qN+r\) i.e. \(n/N=q+r/N\) where \(r\) is the remainder, so the integer part or floor of this is clearly just \(q\) -- the number of times \(N\) goes into \(n\) s

Answer 8

Thanks a ton. I got most of the parts except question 4. What is the logic when saying |O(1) | < G (1) + N ?