= Solution
Write $d=|\Gamma|$ and identify each character with a residue $r_j\in\mathbb Z/N\mathbb Z$. Partition the $d$-dimensional torus into $Q^d$ cubes of side $1/Q$, where $Q$ is comparable to $N^{1/d}$. Applying the <pigeonhole principle> to the points
$$
\left(\frac{kr_1}{N},\ldots,\frac{kr_d}{N}\right),
\qquad 0\leq k\leq Q^d,
$$
gives a nonzero residue $q$ satisfying
$$
\left\|\frac{qr_j}{N}\right\|_{\mathbb R/\mathbb Z}\leq\frac1Q
\qquad(1\leq j\leq d).
$$
Consequently $|e^{2\pi imqr_j/N}-1|\leq\rho$ whenever $|m|\leq\rho Q/(4\pi)$. After allowing for integer parts and the small values of $Q$, this produces the centered <arithmetic progression>
$$
\{-Lq,\ldots,0,\ldots,Lq\}\subseteq B(\Gamma,\rho)
$$
of length at least $\frac18\rho N^{1/d}$.
Solved by gpt-5.6-sol high.
Back to article page
