Return to Answer

This response is in answer to David's further question about whether it is possible to bound the rate at which S_N/N tends to zero, as he was wanting to use Weyl's inequality to do. This is not possible, even in the case d=2 and f(n)=θn². (for d=1 it is not hard to show that S_N is bounded so $S_N/N=O(N^{-1})$). Set $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Given any function h: ℕ → ℝ₊ with liminf_nh(n) = 0, I show that there are irrational θ with $$ \begin{array}{}\displaystyle\sup_N\vert S_N(\theta)/(h(N)N)\vert=\infty.&&(*)\end{array} $$

[Note: The following is a much simpler argument than the original version]. I'll use the Baire category theorem to find counterexamples

For any countable collection A_n of open dense subsets of ℝ, the intersection A = ∩_nA_n is dense in ℝ.

In particular, any such A is nonempty. We can say more than this; if S is a countable subset of the reals then $A\setminus S=\left(\bigcap_nA_n\right)\cap\left(\bigcap_{s\in S}\mathbb{R}\setminus\{s\}\right)$ is an intersection of dense open sets, so is dense. In particular, A will contain a dense set of irrational values.

To construct counterexamples then, it is only necessary to show that the set of all θ at which the sequence diverges to infinity is an intersection of countably many open sets, and show that it contains a dense set of rational numbers. The Baire category theorem implies that it will also diverge at a dense set of irrationals.

In fact, for any sequence x_n(θ) depending continuously on a real parameter θ, the set of values of θ for which it diverges to infinity is an intersection of countably many open sets $$ \{\theta\colon\sup_n\vert x_n(\theta)\vert=\infty\}=\bigcap_n\bigcup_m\{\theta\colon\vert x_m(\theta)\vert>n\\}. $$

So, we only need to find a dense set of rational numbers at which (*) holds.

Let θ = a/b for integers a,b with b > 0. Setting $x=S_b(\theta)/b$ then $S_N(\theta)/N\to x$ as $N\to\infty$.

Proof: If m ≡ n (mod b) then θm² - θn² is an integer, and $e^{2\pi i\theta m^2}=e^{2\pi i \theta n^2}$. So $n\mapsto e^{2\pi i\theta n^2}$ has period b, giving $$ S_{bN}(\theta)=\sum_{j=0}^{N-1}\sum_{k=1}^{b}e^{2\pi i\theta(jb+k)^2}=N\sum_{k=1}^be^{2\pi i\theta k^2}. $$ So, S_bN(θ) = NS_b(θ). Now, any N can be written as N = bM + R for some R < b. Then, $\vert S_N-MS_b\vert\le R$ and, dividing by N gives $\vert S_N/N-S_b/b\vert\to0$ as N goes to infinity.

As |S_N(θ)/(h(N)N)| ∼ |x|/h(N) → ∞ whenever x is nonzero, the following shows that (*) holds whenever θ is of the form a/p for an odd prime p not dividing a. Such rationals are dense, so the existence of irrational θ for which (*) holds follows from the Baire category theorem.

Let θ = a/p for integers a,p with p an odd prime not dividing a. Then $x=S_p(\theta)/p$ is nonzero.

Proof: Note that $u=e^{2\pi i a/p}$ is a primitive p'th root of unity with minimal polynomial $X^{p-1}+X^{p-2}+\cdots+X+1$ over the rationals. Then, all proper subsets of $\{1,u,u^2,\ldots,u^{p-1}\}$ are linearly independent over the rationals and $$ S_p(\theta)=\sum_{k=1}^{p}u^{k^2}=1+2\sum_{k=1}^{(p-1)/2}u^{k^2} $$ is nonzero.

In fact as pointed out by David below, S_p is a Gauss sum and has size √p.

This response is in answer to David's further question about whether it is possible to bound the rate at which S_N/N tends to zero, as he was wanting to use Weyl's inequality to do. This is not possible, even in the case d=2 and f(n)=θn². (for d=1 it is not hard to show that S_N is bounded so $S_N/N=O(N^{-1})$). Set $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Given any function h: ℕ → ℝ₊ with liminf_nh(n) = 0, I show that there are irrational θ with $$ \begin{array}{}\displaystyle\sup_N\vert S_N(\theta)/(h(N)N)\vert=\infty.&&(*)\end{array} $$

[Note: The following is a much simpler argument than the original version]. I'll use the Baire category theorem to find counterexamples

For any countable collection A_n of open dense subsets of ℝ, the intersection A = ∩_nA_n is dense in ℝ.

In particular, any such A is nonempty. We can say more than this; if S is a countable subset of the reals then $A\setminus S=\left(\bigcap_nA_n\right)\cap\left(\bigcap_{s\in S}\mathbb{R}\setminus\{s\}\right)$ is an intersection of dense open sets, so is dense. In particular, A will contain a dense set of irrational values.

To construct counterexamples then, it is only necessary to show that the set of all θ at which the sequence diverges to infinity is an intersection of countably many open sets, and show that it contains a dense set of rational numbers. The Baire category theorem implies that it will also diverge at a dense set of irrationals.

In fact, for any sequence x_n(θ) depending continuously on a real parameter θ, the set of values of θ for which it diverges to infinity is an intersection of countably many open sets $$ \{\theta\colon\sup_n\vert x_n(\theta)\vert=\infty\}=\bigcap_n\bigcup_m\{\theta\colon\vert x_m(\theta)\vert>n\}. $$

So, we only need to find a dense set of rational numbers at which (*) holds.

Let θ = a/b for integers a,b with b > 0. Setting $x=S_b(\theta)/b$ then $S_N(\theta)/N\to x$ as $N\to\infty$.

Proof: If m ≡ n (mod b) then θm² - θn² is an integer, and $e^{2\pi i\theta m^2}=e^{2\pi i \theta n^2}$. So $n\mapsto e^{2\pi i\theta n^2}$ has period b, giving $$ S_{bN}(\theta)=\sum_{j=0}^{N-1}\sum_{k=1}^{b}e^{2\pi i\theta(jb+k)^2}=N\sum_{k=1}^be^{2\pi i\theta k^2}. $$ So, S_bN(θ) = NS_b(θ). Now, any N can be written as N = bM + R for some R < b. Then, $\vert S_N-MS_b\vert\le R$ and, dividing by N gives $\vert S_N/N-S_b/b\vert\to0$ as N goes to infinity.

As |S_N(θ)/(h(N)N)| ∼ |x|/h(N) → ∞ whenever x is nonzero, the following shows that (*) holds whenever θ is of the form a/p for an odd prime p not dividing a. Such rationals are dense, so the existence of irrational θ for which (*) holds follows from the Baire category theorem.

Let θ = a/p for integers a,p with p an odd prime not dividing a. Then $x=S_p(\theta)/p$ is nonzero.

Proof: Note that $u=e^{2\pi i a/p}$ is a primitive p'th root of unity with minimal polynomial $X^{p-1}+X^{p-2}+\cdots+X+1$ over the rationals. Then, all proper subsets of $\{1,u,u^2,\ldots,u^{p-1}\}$ are linearly independent over the rationals and $$ S_p(\theta)=\sum_{k=1}^{p}u^{k^2}=1+2\sum_{k=1}^{(p-1)/2}u^{k^2} $$ is nonzero.

In fact as pointed out by David below, S_p is a Gauss sum and has size √p.

This response is in answer to David's further question about whether it is possible to bound the rate at which $S_N/N$ tends to zero, as he was wanting to use Weyl's inequality to do.

I don't think that it is possible, even in the case d=2 and $f(n)=\theta n^2$. (for d=1 it is not hard to show that $S_N$ is bounded so $S_N/N=O(N^{-1})$). [It took a few edits, but hopefully this answer is free of major errors now] $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Then, I'll try to show that, for any given h(N)->0, it is not true that $S_N(\theta)/N$ always tends to zero at rate O(h(N)).

(1) Let $h\colon\mathbb{N}\to\\mathbb{R}_+$ satisfy $\lim_nh(n)=0$. Then, there exists an irrational $\theta$ such that $\sup_N\vert S_N(\theta)/(h(N)N)\vert=\infty$

I'll construct this by choosing θ as the limit of a very quickly converging sequence of rational numbers. Let's break up the construction, starting with the case where θ is actually rational.

(2) Let θ = a/b for integers a,b with b > 0. Setting $x=S_b(\theta)/b$ then $S_N(\theta)/N\to x$ as $N\to\infty$.

Proof: If m ≡ n (mod b) then m² ≡ n² (mod b), so θm² - θn² is an integer, and $e^{2\pi i\theta m^2}=e^{2\pi i \theta n^2}$. This shows that $n\mapsto e^{2\pi i\theta n^2}$ has period b. This gives $$ S_{bN}(\theta)=\sum_{j=0}^{N-1}\sum_{k=1}^{b}e^{2\pi i\theta(jb+k)^2}=N\sum_{k=1}^be^{2\pi i\theta k^2}. $$ So, S_bN(θ) = NS_b(θ). Now, any N can be written as N = bM + R for some R < b. Then, $\vert S_N-MS_b\vert\le R$ and, dividing by N gives $\vert S_N/N-S_b/b\vert\to0$ as N goes to infinity.

(3) Let θ = a/b for integers a,b with b a product of distinct odd primes. Then $x=S_b(\theta)/b$ is nonzero and, by (2), $S_N(\theta)/N$ tends to a nonzero limit.

Proof: If c,d are coprime positive integers then, by the Chinese remainder theorem, every 0≤n<cd can be written as n≡vc+wd (mod cd) for integers 0≤v<d and 0≤w<c. If, furthermore, θ is such that cdθ is an integer then, $$ \begin{align} S_{cd}(\theta)&=\sum_{w=0}^{c-1}\sum_{v=0}^{d-1}e^{2\pi i\theta(vc+wd)^2}\\\\ &=\sum_{w=0}^{c-1}e^{2\pi i\theta d^2 w^2}\sum_{v=0}^{d-1}e^{2\pi i\theta c^2 v^2}\\\\ &=S_c(\theta d^2)S_d(\theta c^2) \end{align} $$ We want to show that $S_b(\theta)\not=0$ whenever bθ is an integer and b is a product of distinct odd primes. By breaking b down into its prime factors and using the identity above, we reduce the problem to that where b is an odd prime.

So, suppose that b is an odd prime, and set $u=e^{2\pi i a/b}$. We suppose that b does not divide a (otherwise $S_b(\theta)$ is strictly positive), so u is a primitive b'th root of unity with minimal polynomial $X^{b-1}+X^{b-2}+\cdots+X+1$ over the rationals. Then, all proper subsets of $\{1,u,u^2,\ldots,u^{b-1}\}$ are linearly independent over the rationals and $$ S_b(\theta)=\sum_{k=1}^{b}u^{k^2}=1+2\sum_{k=1}^{(b-1)/2}u^{k^2} $$ is nonzero.

Using this, a θ can be constructed proving (1) above.

Let $h\colon\mathbb{N}\to\mathbb{R}$ satisfy $\lim_nh(n)=0$. Then, there exists a sequence $p_k$ of prime numbers, tending to infinity, such that the sum $$ \begin{array} {}\displaystyle\theta=\sum_{n=1}^\infty\frac{1}{p_n}&&(*) \end{array} $$ converge to an irrational number, and $\sup_NS_N(\theta)/(h(N)N)=\infty$.

Proof: In order for the sum in (*) to converge, we have to require that p_n grows quickly, such as p_n ≥ 2ⁿ. Now, let us choose p₁,p₂,... inductively. Suppose that odd primes p₁,...,p_m have already been chosen, and set $\theta_m=1/p_1+\cdots+1/p_m$. We can write θ_m=a_m/b_m where b_m=p₁...p_m. If we make sure that $p_n>2^{n-m}b_m^m$ for all n>m, this will give the following rational approximations $$ \vert\theta-a_m/b_m\vert=\sum_{k=m+1}^\infty \frac{1}{p_k}\le\frac{1}{b_m^m} $$ and, by Liouville's theorem, θ will be irrational (transcendental, in fact).

By (3) above, $S_N(\theta_m)/N$ converges to a nonzero limit as N goes to infinity, so we can choose an $N_m$ with $\vert S_{N_m}(\theta_m)/(h(N_m)N_m)\vert>m$. By continuity, there is an $\epsilon>0$ such that $\vert S_{N_m}(\theta)/{N_m}\vert>m$ whenever $\vert\theta-\theta_m\vert\le\epsilon$. To guarantee that our value of θ defined by (*) satisfies this, it is only necessary to choose $p_n>2^{n-m}/\epsilon$ for all n > m.

Proceeding in this way, we can choose a quickly increasing sequence of prime numbers, where each choice of prime number imposes a lower bound on the following terms in the sequence. It also provides us with a sequence N₁,N₂,... of integers such that $\vert S_{N_m}(\theta)/{(h(N_m)N_m)}\vert\ge m$, so $\sup_N\vert S_N(\theta)/(h(N)N)\vert=\infty$.

This response is in answer to David's further question about whether it is possible to bound the rate at which S_N/N tends to zero, as he was wanting to use Weyl's inequality to do. This is not possible, even in the case d=2 and f(n)=θn². (for d=1 it is not hard to show that S_N is bounded so $S_N/N=O(N^{-1})$). Set $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Given any function h: ℕ → ℝ₊ with liminf_nh(n) = 0, I show that there are irrational θ with $$ \begin{array}{}\displaystyle\sup_N\vert S_N(\theta)/(h(N)N)\vert=\infty.&&(*)\end{array} $$

[Note: The following is a much simpler argument than the original version]. I'll use the Baire category theorem to find counterexamples

For any countable collection A_n of open dense subsets of ℝ, the intersection A = ∩_nA_n is dense in ℝ.

In particular, any such A is nonempty. We can say more than this; if S is a countable subset of the reals then $A\setminus S=\left(\bigcap_nA_n\right)\cap\left(\bigcap_{s\in S}\mathbb{R}\setminus\{s\}\right)$ is an intersection of dense open sets, so is dense. In particular, A will contain a dense set of irrational values.

To construct counterexamples then, it is only necessary to show that the set of all θ at which the sequence diverges to infinity is an intersection of countably many open sets, and show that it contains a dense set of rational numbers. The Baire category theorem implies that it will also diverge at a dense set of irrationals.

In fact, for any sequence x_n(θ) depending continuously on a real parameter θ, the set of values of θ for which it diverges to infinity is an intersection of countably many open sets $$ \{\theta\colon\sup_n\vert x_n(\theta)\vert=\infty\}=\bigcap_n\bigcup_m\{\theta\colon\vert x_m(\theta)\vert>n\\}. $$

So, we only need to find a dense set of rational numbers at which (*) holds.

Let θ = a/b for integers a,b with b > 0. Setting $x=S_b(\theta)/b$ then $S_N(\theta)/N\to x$ as $N\to\infty$.

Proof: If m ≡ n (mod b) then θm² - θn² is an integer, and $e^{2\pi i\theta m^2}=e^{2\pi i \theta n^2}$. So $n\mapsto e^{2\pi i\theta n^2}$ has period b, giving $$ S_{bN}(\theta)=\sum_{j=0}^{N-1}\sum_{k=1}^{b}e^{2\pi i\theta(jb+k)^2}=N\sum_{k=1}^be^{2\pi i\theta k^2}. $$ So, S_bN(θ) = NS_b(θ). Now, any N can be written as N = bM + R for some R < b. Then, $\vert S_N-MS_b\vert\le R$ and, dividing by N gives $\vert S_N/N-S_b/b\vert\to0$ as N goes to infinity.

As |S_N(θ)/(h(N)N)| ∼ |x|/h(N) → ∞ whenever x is nonzero, the following shows that (*) holds whenever θ is of the form a/p for an odd prime p not dividing a. Such rationals are dense, so the existence of irrational θ for which (*) holds follows from the Baire category theorem.

Let θ = a/p for integers a,p with p an odd prime not dividing a. Then $x=S_p(\theta)/p$ is nonzero.

Proof: Note that $u=e^{2\pi i a/p}$ is a primitive p'th root of unity with minimal polynomial $X^{p-1}+X^{p-2}+\cdots+X+1$ over the rationals. Then, all proper subsets of $\{1,u,u^2,\ldots,u^{p-1}\}$ are linearly independent over the rationals and $$ S_p(\theta)=\sum_{k=1}^{p}u^{k^2}=1+2\sum_{k=1}^{(p-1)/2}u^{k^2} $$ is nonzero.

In fact as pointed out by David below, S_p is a Gauss sum and has size √p.

I don't think that it is possible, even in the case d=2 and $f(n)=\theta n^2$. (for d=1 it is not hard to show that $S_N$ is bounded so $S_N/N=O(N^{-1})$). [Edit: There is an error below, but I'm hopeful it can be fixed]. I'll write $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Then, I'll try to show that, for any given h(N)->0, it is not true that $S_N(\theta)/N$ always tends to zero at rate O(h(N)).

(3) Let θ = a/b for coprime integers a,b with b odd and φ(b)≥b/2 (φ is Euler's totient function. Then $x=S_b(\theta)/b$ is nonzero and, by (2), $S_N(\theta)/N$ tends to a nonzero limit.

Proof: As a,b are coprime, $u=e^{2\pi i \theta}$ is a primitive b'th root of unity, with minimal polynomial of degree φ(b)≥b/2 over the rationals. So $$ S_b(\theta)=\sum_{k=1}^{b}u^{k^2}=1+2\sum_{k=1}^{(b-1)/2}u^{k^2} $$ is nonzero. [Edit: There is still an error here. I need to show that $\{u^{k^2}\colon k=0,\ldots,(b-1)/2\}$ is linearly independent over the rationals, which I haven't done. Hopefully this can be fixed]

Proof: In order for the sum in (*) to converge, we have to require that p_n grows quickly, such as p_n ≥ 2ⁿ. Now, let us choose p₁,p₂,... inductively. Suppose that odd primes p₁,...,p_m have already been chosen, and set $\theta_m=1/p_1+\cdots+1/p_m$. We can write θ_m=a_m/b_m where b_m=p₁...p_m. If we make sure that $p_m>2^{m-n}b_n^n$ for all m>n, this will give the following rational approximations $$ \vert\theta-a_m/b_m\vert=\sum_{k=n+1}^\infty \frac{1}{p_k}\le\frac{1}{p_n}^n $$ and, by Liouville's theorem, θ will be irrational (transcendental, in fact).

Also, assuming that p_n are chosen large enough that $\prod_n(1-1/p_n)>1/2$ then we have φ(b_m) ≥ b_m/2 and (3) can be applied. By (3), $S_N(\theta_m)/N$ converges to a nonzero limit, so we can choose an $N_m$ with $\vert S_{N_m}(\theta_m)/(h(N_m)N_m)\vert>m$. By continuity, there is an $\epsilon>0$ such that $\vert S_{N_m}(\theta)/{N_m}\vert>m$ whenever $\vert\theta-\theta_m\vert\le\epsilon$. To guarantee that our value of θ defined by (*) satisfies this, it is only necessary to choose $p_n>2^{n-m}/\epsilon$ for all n > m.

I don't think that it is possible, even in the case d=2 and $f(n)=\theta n^2$. (for d=1 it is not hard to show that $S_N$ is bounded so $S_N/N=O(N^{-1})$). [It took a few edits, but hopefully this answer is free of major errors now] $$ S_N(\theta)=\sum_{n=1}^Ne^{2\pi i\theta n^2} $$ in the following. Then, I'll try to show that, for any given h(N)->0, it is not true that $S_N(\theta)/N$ always tends to zero at rate O(h(N)).

(3) Let θ = a/b for integers a,b with b a product of distinct odd primes. Then $x=S_b(\theta)/b$ is nonzero and, by (2), $S_N(\theta)/N$ tends to a nonzero limit.

Proof: If c,d are coprime positive integers then, by the Chinese remainder theorem, every 0≤n<cd can be written as n≡vc+wd (mod cd) for integers 0≤v<d and 0≤w<c. If, furthermore, θ is such that cdθ is an integer then, $$ \begin{align} S_{cd}(\theta)&=\sum_{w=0}^{c-1}\sum_{v=0}^{d-1}e^{2\pi i\theta(vc+wd)^2}\\\\ &=\sum_{w=0}^{c-1}e^{2\pi i\theta d^2 w^2}\sum_{v=0}^{d-1}e^{2\pi i\theta c^2 v^2}\\\\ &=S_c(\theta d^2)S_d(\theta c^2) \end{align} $$ We want to show that $S_b(\theta)\not=0$ whenever bθ is an integer and b is a product of distinct odd primes. By breaking b down into its prime factors and using the identity above, we reduce the problem to that where b is an odd prime.

So, suppose that b is an odd prime, and set $u=e^{2\pi i a/b}$. We suppose that b does not divide a (otherwise $S_b(\theta)$ is strictly positive), so u is a primitive b'th root of unity with minimal polynomial $X^{b-1}+X^{b-2}+\cdots+X+1$ over the rationals. Then, all proper subsets of $\{1,u,u^2,\ldots,u^{b-1}\}$ are linearly independent over the rationals and $$ S_b(\theta)=\sum_{k=1}^{b}u^{k^2}=1+2\sum_{k=1}^{(b-1)/2}u^{k^2} $$ is nonzero.

Proof: In order for the sum in (*) to converge, we have to require that p_n grows quickly, such as p_n ≥ 2ⁿ. Now, let us choose p₁,p₂,... inductively. Suppose that odd primes p₁,...,p_m have already been chosen, and set $\theta_m=1/p_1+\cdots+1/p_m$. We can write θ_m=a_m/b_m where b_m=p₁...p_m. If we make sure that $p_n>2^{n-m}b_m^m$ for all n>m, this will give the following rational approximations $$ \vert\theta-a_m/b_m\vert=\sum_{k=m+1}^\infty \frac{1}{p_k}\le\frac{1}{b_m^m} $$ and, by Liouville's theorem, θ will be irrational (transcendental, in fact).

By (3) above, $S_N(\theta_m)/N$ converges to a nonzero limit as N goes to infinity, so we can choose an $N_m$ with $\vert S_{N_m}(\theta_m)/(h(N_m)N_m)\vert>m$. By continuity, there is an $\epsilon>0$ such that $\vert S_{N_m}(\theta)/{N_m}\vert>m$ whenever $\vert\theta-\theta_m\vert\le\epsilon$. To guarantee that our value of θ defined by (*) satisfies this, it is only necessary to choose $p_n>2^{n-m}/\epsilon$ for all n > m.