A Deep Dive with Python
Exponential sums appear across analytic number theory, signal processing, and cryptography. The central challenge is simple to state but rich in depth: how small can we guarantee these sums to be? In this post, we tackle a concrete problem, derive classical upper bounds, and visualize the geometry behind the estimates.
What Are Exponential Sums?
Given a function $f: {0, 1, \dots, N-1} \to \mathbb{R}$, the exponential sum is defined as:
$$S(f, N) = \sum_{n=0}^{N-1} e^{2\pi i f(n)}$$
The key insight is that each term $e^{2\pi i f(n)}$ is a unit complex number — a point on the unit circle. The sum $S(f, N)$ measures how much cancellation occurs. Perfect cancellation gives $S = 0$; perfect alignment gives $|S| = N$.
The Problem: Weyl Sums
We focus on Weyl sums (polynomial phase exponential sums):
$$S(\alpha, N) = \sum_{n=0}^{N-1} e^{2\pi i \alpha n^2}$$
where $\alpha \in \mathbb{R}$. The goal is to bound $|S(\alpha, N)|$ from above, uniformly or for specific $\alpha$.
Trivial bound: $|S(\alpha, N)| \leq N$.
Weyl’s bound (the key classical result): For $\alpha = p/q$ in lowest terms,
$$|S(\alpha, N)| \lesssim N \left( \frac{1}{q} + \frac{1}{N} + \frac{q}{N^2} \right)^{1/4}$$
When $q \sim N$, this gives $|S| \lesssim N^{3/4}$, a genuine savings over the trivial bound.
Source Code
1 | import numpy as np |
Code Walkthrough
Section 1 — Core Functions
weyl_sum_vectorized(alpha_arr, N) is the workhorse. It builds the phase matrix $\phi_{a,n} = 2\pi \alpha_a n^2$ via np.outer, wraps it into complex exponentials with a single np.exp call, and sums along the $n$-axis. This avoids Python loops entirely — computing 2,000 values of $|S|$ for $N=300$ takes under a second instead of minutes.
weyl_bound(alpha, N) implements the classical estimate. Given $\alpha$, it finds the best rational approximation $p/q$ with $q \leq N$ using Python’s Fraction.limit_denominator, then evaluates
$$N \left(\frac{1}{q} + \frac{1}{N} + \frac{q}{N^2}\right)^{1/4}$$
The small $\epsilon$ in the denominator prevents division-by-zero when $\alpha$ is exactly rational.
Section 2 — Experiment A: Sweep over $\alpha$
We sample 2,000 values of $\alpha \in [0,1)$ and compute both $|S(\alpha, N)|$ and the Weyl bound. The key observation is that $|S|$ spikes near rational numbers with small denominators (e.g., $\alpha = 1/2, 1/3, 2/3, 1/4, \dots$) — exactly where the unit-circle vectors nearly align. The Weyl bound captures this: small $q$ inflates the bound.
Section 3 — Experiment B: Scaling with $N$
We fix $\alpha = \sqrt{2} - 1$ (a badly approximable irrational, with continued fraction $[0; 2, 2, 2, \dots]$) and grow $N$ from 10 to 800. We compare $|S|$ against the reference curves $N^{1/2}$, $N^{3/4}$, and $N^1$. The actual sum tracks closer to $N^{3/4}$ than to $N$, confirming the Weyl bound is non-trivial.
The log-log panel makes the exponent visually readable: the slope of $\log|S|$ vs $\log N$ estimates the true growth exponent.
Section 4 — Experiment C: 3-D Landscape
We compute $|S(\alpha, N)| / N$ on a grid of $120 \times 20$ points $(\alpha, N)$ and render it as a 3-D surface with plot_surface. The normalized quantity lies in $[0, 1]$, where 1 means perfect alignment and 0 means perfect cancellation. The ridge structure along rational $\alpha$ values is immediately visible in the surface.
Section 5 — Experiment D: Random Walk
Each term $e^{2\pi i \alpha n^2}$ is a unit step in $\mathbb{C}$. We plot the partial sums (the walk path) and color steps by their index $n$. The final point’s distance from the origin is exactly $|S(\alpha, N)|$. This panel makes the cancellation mechanism geometric and intuitive: the walk spirals back toward the origin when phases distribute well.
Results
Done.
Graph Commentary
Panel 1 (top-left): The jagged blue curve of $|S(\alpha, N)|$ stays well below the yellow trivial bound $N = 300$ almost everywhere. Tall spikes appear exactly at $\alpha = 0, 1/2, 1/3, 2/3, 1/4, \dots$ The red Weyl bound tracks the spike heights faithfully.
Panel 2 (top-right): Zooming near $\alpha = 1/3$ reveals a sharp, symmetric spike. The Weyl bound rises toward $\alpha = 1/3$ and falls away — this is the rational approximability signature. The exact spike value is $|S(1/3, N)|$, which can be computed in closed form via Gauss sum theory.
Panel 3 (middle-left): For irrational $\alpha = \sqrt{2}-1$, the actual $|S|$ grows roughly as $N^{3/4}$, matching the dashed purple reference. The trivial bound $N$ is always far above — the Weyl bound gives a genuine improvement.
Panel 4 (middle-right): On log-log axes, the slope of the blue $|S|$ curve sits between $1/2$ and $3/4$, confirming sub-linear growth. The true exponent for this particular $\alpha$ is an open problem (the Lindelöf-type conjecture predicts exponents approaching $1/2$).
Panel 5 (bottom-left, 3-D): The $(\alpha, N)$ landscape shows a mountain-range structure: ridges rise along rational $\alpha$ values, and the surface decays as $N$ grows (more cancellation at large $N$). The plasma colormap maps normalized $|S|/N$ from 0 (black/purple) to 1 (yellow).
Panel 6 (bottom-right): The complex-plane random walk for $\alpha = \sqrt{3}/7$ spirals inward over 150 steps. The red star (end point) sits close to the origin — strong cancellation. The color gradient from purple (early steps) to cyan (late steps) shows the walk eventually doubling back on itself.
Key Takeaways
The Weyl bound tells us:
$$|S(\alpha, N)| \ll N^{3/4}$$
when $\alpha$ is irrational. The exact exponent depends on the Diophantine approximation quality of $\alpha$: better approximable irrationals (like Liouville numbers) can produce larger sums, while “badly approximable” numbers like $\sqrt{2}-1$ saturate the bound. Improving the exponent from $3/4$ toward $1/2$ is one of the central open problems in analytic number theory, connected to the Riemann Hypothesis through the theory of the Riemann zeta function on the critical line.