The Pólya–Vinogradov inequality with $\log\log q$

Introduction

Let $\chi$ be a primitive Dirichlet character modulo $q \ge3$. The Pólya–Vinogradov inequality states that $\left|\sum_{n\le x}\chi(n)\right| \ll\sqrt{q}\log q$ uniformly in $x$.¹ Paley proved that the factor $\log q$ cannot be replaced by anything smaller than $\log\log q$: for infinitely many primitive quadratic characters the maximum over $x$ exceeds $c\sqrt{q}\log\log q$.² Montgomery and Vaughan [2] proved the upper bound $\sqrt{q}\log\log q$ under the generalised Riemann hypothesis. Without hypothesis, Granville and Soundararajan lowered the exponent of $\log q$ for characters of fixed odd order.³ We prove the bound of Montgomery and Vaughan for every primitive character.

By Paley’s theorem, Theorem 1.1 is optimal up to the value of $C$. The input that replaces the Riemann hypothesis is the following theorem.

Theorem 1.2 is proved, and formalised in Lean 4, in [3]. It is the only result we use without proof; everything else is proved below from first principles, and the constants are effective.

Montgomery and Vaughan use the Riemann hypothesis in one place: on the major arcs, for prime sums of the characters $\chi\psi$ twisted by additive characters, where $\psi$ runs over the characters of a small modulus $r$. A power saving in these sums is enough there, and Theorem 1.2 provides one (Corollary 3.8). On the minor arcs they use their unconditional bound for exponential sums with multiplicative coefficients. A weaker form of it suffices, and we prove that form in § 4 with Selberg’s sieve as the only arithmetic input. Figure 1 shows how the parts fit together.

The same half-plane controls the logarithmic derivative of $L(s,\chi)$ at $s = 1$. For a number field $K$ write $\zeta_K(s) = c_{-1}(s - 1)^{-1} + c_0 + O(s - 1)$ near $s = 1$; the Euler–Kronecker constant of $K$ is $\gamma_K = c_0/c_{-1}$. Let $\gamma_q$ be the Euler–Kronecker constant of $\mathbb{Q}(\zeta_q)$. For a prime $q$ the factorisation $\zeta_{\mathbb{Q}(\zeta_q)}(s)=\zeta(s)\prod_{\chi\ne\chi_0}L(s,\chi)$, the product over the nonprincipal characters modulo $q$,⁴ gives

where $\gamma$ is Euler’s constant.

Under the generalised Riemann hypothesis the bound (i) is classical, Ihara proved $\gamma_q\le(2+o(1))\log q$ and Badzyan proved a lower bound of the order of (ii);⁵ Ford, Luca and Moree proved the two bounds of (ii) without hypothesis for a set of primes $q$ of density one.⁶ For all primes the best unconditional bound we know is $|\gamma_q|\ll_\varepsilon q^\varepsilon$, due to Ihara, Murty and Shimura [1]. The upper bound in (ii) needs only Chebyshev’s bound. The lower bound needs an upper bound for the prime powers $n\le q^{17}$ with $n\equiv1\pmod q$, which we obtain from Selberg’s sieve applied in dyadic blocks (Lemma 6.3).

We have not found Theorem 1.1 or Theorem 1.3 among the consequences of Theorem 1.2 drawn in [3] or in the work that followed it. The arguments work, with other constants, whenever $L(s,\chi)\ne0$ on $\operatorname{Re}s>\theta$ for all nonprincipal $\chi$ and some fixed $\theta<1$.

The paper is organised as follows. Section 2 collects Chebyshev’s bounds and Selberg’s sieve. Section 3 bounds Riesz means of $\chi\Lambda$ by a contour shift. Section 4 proves the bound for exponential sums with multiplicative coefficients, Section 5 proves Theorem 1.1 and Section 6 proves Theorem 1.3.

Preliminaries

Throughout, $p$ and $\ell$ denote primes, $\Lambda$ is the von Mangoldt function, $\theta(x)=\sum_{p\le x}\log p$, $\psi(x)=\sum_{n\le x}\Lambda(n)$, $e(x)=e^{2\pi ix}$, and $\lVert x\rVert$ is the distance from $x$ to the nearest integer. We write $\omega(n)$ for the number of prime factors of $n$, $\tau_3(n)$ for the number of ordered factorisations $n=abc$, and $P(n)$ for the largest prime factor of $n\ge2$, with $P(1)=1$.

Proof. (i) It suffices to treat integers $m\ge1$, and we use induction on $m$. The cases $m=1,2$ are clear, and for even $m>2$ we have $\theta(m)=\theta(m-1)$. Let $m=2n+1$. The primes in $(n+1,2n+1]$ divide $\binom{2n+1}{n}$, and $2\binom{2n+1}{n}\le2^{2n+1}$ because $\binom{2n+1}{n}$ and $\binom{2n+1}{n+1}$ are equal terms of the binomial expansion of $(1+1)^{2n+1}$. Hence $\theta(2n+1)\le\theta(n+1)+n\log4\le(2n+1)\log4$.

(ii) We have $\psi(x)-\theta(x)=\sum_{k\ge2}\theta(x^{1/k})$, where only $k\le\log x/\log2$ contribute. Each term is at most $\sqrt{x}\log4$ by (i), so the sum is at most $(\log x/\log2)\sqrt{x}\log4=2\sqrt{x}\log x$. Since $\log x\le\sqrt{x}$, $\psi(x)\le(\log4+2)x\le4x$.

(iii) By Legendre’s formula and (i),

(iv) Let $A(u)=\sum_{p\le u}\log p/p$. Partial summation and (iii) give

and the integral is at most $\log\log N-\log\log2+2$. □

We use Selberg’s upper bound sieve in the following form.⁷

$\nu(p))$. Then

Proof. Let $D$ be the set of divisors $d$ of $P$ with $d\le\sqrt{y}$, and let $(\lambda_d)_{d\in D}$ be real numbers with $\lambda_1=1$. If $(a_n,P)=1$ then $\sum_{\substack{d\in D,\,d\mid a_n}}\lambda_d=1$, and otherwise this sum is real, so

Write $Q$ for the double sum in the first term. Since $\nu$ is multiplicative and $d_1,d_2$ are squarefree, $\nu([d_1,d_2])=\nu(d_1)\nu(d_2)/\nu((d_1,d_2))$. Let $h$ be the multiplicative function on the divisors of $P$ with $h(p)=1/\nu(p)-1=1/g(p)$; then $1/\nu(m)=\sum_{l\mid m}h(l)$ for $m\mid P$, and

Möbius inversion gives $\lambda_d\nu(d)=\sum_{\substack{l\in D,\,d\mid l}}\mu(l/d)y_l$, so the condition $\lambda_1=1$ reads $\sum_{l\in D}\mu(l)y_l=1$. By Cauchy’s inequality

with equality for $y_l=\mu(l)g(l)/S$. We make this choice, so that $Q=1/S$. Then, writing $l=de$,

Since $g(d)/\nu(d)=\prod_{p\mid d}(1-\nu(p))^{-1}=\prod_{p\mid d}(1+g(p))=\sum_{f\mid d}g(f)$, we get $|\lambda_d|\le S^{-1}\sum_{f\mid d}\sum_e g(fe)$, and the products $fe$ are distinct elements of $D$; hence $|\lambda_d|\le1$. Finally $[d_1,d_2]\le d_1d_2\le y$, and every $d\mid P$ is the least common multiple of at most $3^{\omega(d)}$ pairs $(d_1,d_2)$, so the second term is at most $\sum_{\substack{d\mid P\\d\le y}}3^{\omega(d)}|R_d|$.

Riesz means of prime sums

For an arithmetic function $a$ and $x \ge1$ put

The weight $1-n/x$ makes the Mellin kernel absolutely integrable, which keeps the contour shift below free of truncation errors. The aim of this section is Proposition 3.7.

Proof. For $\operatorname{Re}s \ge1$ we have $|\chi(\ell)\ell^{-s}| \le1/2$, and $|\log(1-w)| \le\sum_k |w|^k/k \le\frac{3}{2}|w|$ for $|w| \le1/2$. The series therefore converges locally uniformly on $\operatorname{Re}s > 1$ and is bounded by $A_0$ on $\operatorname{Re}s \ge3/2$, and the Euler product gives $e^E=L$.

Proof. We have $\log(2q) \le2\log(q+2)$, and $\log y \le2y^{1/2}$ with $3+|t| \le4(1+|t|)$ gives $\log(3+|t|) \le4(1+|t|)^{1/2}$; the first bound follows from $\log(q+2) \ge1$. For the second, $|s| \ge\max(\sigma,|t|) \ge(1+|t|)/4$ and $|s+1| \ge\max(\sigma+1,|t|) \ge(1+|t|)/2$.

Proof. Put $\sigma_0=a+8\delta$ and

For $\operatorname{Re}s>1$, $-L'/L(s,\chi)=\sum_n\chi(n)\Lambda(n)n^{-s}$, so Lemma 3.1(ii) gives $S(\chi;x)=\frac{1}{2\pi}\int_{\mathbb{R}}\Phi(2+it)\,dt$. The function $\Phi$ is holomorphic on $\sigma_0 \le\operatorname{Re}s \le2$, and by Lemmas 3.5 and 3.6,

This tends to $0$ as $|t| \to\infty$ uniformly in $\sigma$, so Cauchy’s theorem on the rectangles $[\sigma_0,2]\times[-T,T]$, $T\to\infty$, moves the integral to $\operatorname{Re}s=\sigma_0$ (Figure 2). Since $\int_{\mathbb{R}}(1+|t|)^{-3/2}\,dt=4$, we get $|S(\chi;x)| \le\frac{160K_1}{\pi}x^{\sigma_0}\log(q+2)$.

From now on fix $\delta=1/2000$ and $a=7/8-1/1000$, so that $a+2\delta=7/8$ and

and let $K$ be the constant of Proposition 3.7 for this $\delta$. By Theorem 1.2, Proposition 3.7 applies to every nonprincipal character.

Proof. (i) is Proposition 3.7. For (ii) put $T(y)=yS(\xi;y)$, that is, $T(y)=\sum_{n\le y}\xi(n)\Lambda(n)(y-n)$, and let $0<h\le x$. Then

and the last sum has at most $h+1$ terms, each of modulus at most $h\log(2x)$. With $|T(y)|\le Ky^{1+\sigma_0}\log(k+2)$ this gives

Take $h=x^{47/50}$. Since $1+\sigma_0-47/50<19/20$ and $\log(2x)\le1+100x^{1/100}$, the right side is at most $(8K+202)x^{19/20}\log(k+2)$. The prime powers contribute at most $\psi(x)-\theta(x)\le2\sqrt{x}\log x\le200x^{19/20}$ by Lemma 2.1(ii), and (ii) follows with $C_3=8K+402$.

(iii) Let $\Pi(u)=\sum_{p\le u}\xi(p)\log p$ and $f(u)=e(u\gamma)/\log u$. Partial summation gives

and $|f'(u)|\le2\pi|\gamma|/\log A+1/(u\log^2u)$ for $u\ge A$. By (ii) the right side is at most $C_3B^{19/20}\log(k+2)(3+2\pi|\gamma|B)/\log A$, which gives (2). $\square$

Exponential sums with multiplicative coefficients

For $M>0$ put $w_M(\theta)=M$ if $\lVert\theta\rVert<1/M$ and $w_M(\theta)=1/\lVert\theta\rVert$ otherwise; then $0\le w_M(\theta)\le M$ and $w_M(-\theta)=w_M(\theta)$.

Montgomery and Vaughan [2 Corollary 1] proved this for multiplicative $f$ with $N(\log R)^{3/2}R^{-1/2}$ in place of $N(\log N)^2R^{-1/4}$. The proof below follows their approach, a bilinear decomposition together with the spacing of the multiples of $\alpha$ and an upper bound for prime pairs, with cruder estimates, which suffice for Theorem 1.1.

Proof. (i) Let $z$ be the integer nearest to $k\alpha$. Since $0<|k|<r$ and $(a,r)=1$, $r\nmid ka$, so $|ka/r-z|\ge1/r$ and $\|k\alpha\|\ge1/r-|k||\alpha-a/r|\ge1/(2r)$.

(ii) Let $L=\lfloor r/2\rfloor$, so $L\ge r/4$. For $k$ in a block of $L$ consecutive integers let $y_k=k\alpha-z_k$ with $z_k$ the integer nearest to $k\alpha$. For $k\ne k'$ in the block, $0<|k-k'|<L\le r/2$ and $y_k-y_{k'}\equiv(k-k')\alpha\pmod1$, so $|y_k-y_{k'}|\ge1/(2r)$ by (i). Points of $(-t,t)$ at mutual distances at least $1/(2r)$ number at most $4rt+1$, and $[1,H]$ is covered by at most $H/L+1\le4H/r+1$ blocks.

(iii) If $\|\theta\|\ge1/M$, let $k\ge1$ be least with $\|\theta\|<2^k/M$; then $k\le K$ because $\|\theta\|\le1/2<2^K/M$, and $\|\theta\|\ge2^{k-1}/M$, so $w_M(\theta)\le2^{1-k}M$. Hence

Summing over $h\le H$ with (ii), the first sum is at most $(4H/r+1)(4r+M+\sum_{k\le K}(8r+2^{1-k}M))$ and the second at most $(4H/r+1)(4rM+M^2+\sum_{k\ge1}(16rM2^{-k}+4M^24^{-k}))$.

Lemma 4.3

Let $\theta,\alpha\in\mathbb{R}$, $U>0$, and let $A,B,N$ be nonnegative integers with $B\le A+U$.

(i)

(ii) For a finite set $V$ of positive integers and $b:V\to\mathbb{C}$,

(iii) For $M > 0$ and an integer $H \ge0$,

Proof. (i) If $\lVert\theta\rVert< 1/U$, the sum has at most $U$ terms of modulus 1. Otherwise $\theta\notin\mathbb{Z}$, the sum has modulus at most $\lvert e((B-A)\theta)-1\rvert/\lvert e(\theta)-1\rvert$, and $\lvert e(\theta)-1\rvert=2\lvert\sin\pi\theta\rvert\ge4\lVert\theta\rVert$, so the modulus is at most $1/(2\lVert\theta\rVert)$. (ii) Expanding the square gives $\sum_{v,v'}b(v)b(v')\sum_u e(u(v-v')\alpha)$, where $u$ runs over the integers of $(A,\min(B,N/v,N/v')]$, an interval of length at most $U$; apply (i). (iii) For fixed $m$, the term $m'=m$ is $w_M(0)=M$, and each $h=\lvert m-m'\rvert\in[1,H]$ arises from at most two $m'$.

Proof. Write $S\log N=S_1+S_2$ with $S_1=\sum_{n\le N}f(n)e(n\alpha)\log n$ and $S_2=\sum_{n\le N}f(n)e(n\alpha)\log(N/n)$. Then $\lvert S_2\rvert\le N\log N-\log N!\le N$, since $N^N/N!\le e^N$. In $S_1$ write $\log n=\sum_{d\mid n}\Lambda(d)$ and $n=dm$; complete multiplicativity gives $\sum_{d\le N}\Lambda(d)f(d)\sum_{m\le N/d}f(m)e(dm\alpha)$. The terms with $d$ prime form the sum in the statement, and the others have modulus at most $N\sum_p\sum_{k\ge2}\log p/p^k\le2N\sum_p\log p/p^2\le4\zeta(3/2)N$, since $\log p\le2\sqrt p$.

Let $G(h)=\prod_{p\mid h}p/(p-1)$.

Proof. (i) Apply Lemma 2.2 to $a_n=n(n+h)$, $0\le n<X$, with $y=X^{1/5}$, $z=\lfloor y\rfloor$, $P$ the product of the primes $p\le z$ with $p\nmid h$, and $\nu(d)=2^{\omega(d)}/d$. Every $p\mid P$ is odd, so $\nu(p)=2/p<1$. For $d\mid P$ the residues $n$ with $d\mid n(n+h)$ form $2^{\omega(d)}$ classes modulo $d$ (namely $n\equiv0$ or $-h\pmod p$ for each $p\mid d$, distinct as $p\nmid h$), and each class contains between $X/d-1$ and $X/d+1$ of the integers $0\le n<X$; hence $\lvert R_d\rvert\le2^{\omega(d)}$. Since the prime factors of $d$ are at least 3, $3^{\omega(d)}\lvert R_d\rvert\le6^{\omega(d)}\le d^2\le y^2$, and the error term is at most $y^3=X^{3/5}$.

Let $\mathcal{M}$ be the set of $m\le\sqrt y$ whose prime factors divide $P$. Since

and $\nu(m)=2^{\Omega(m)}/m$ for these $m$, $g(l)$ is the sum of $2^{\Omega(m)}/m$ over the $m$ whose set of prime factors is that of $l$. An $m \in\mathcal{M}$ is counted in $g(l)$ for $l$ the product of its prime factors, and $l \le m \le\sqrt{y}$. Hence, with $\tau(m) \le2^{\Omega(m)}$ the number of divisors of $m$,

Let $T=\lfloor y^{1/4}\rfloor$ and let $B$ be the set of $b\le T$ that are prime to $h$; these $b$ are odd. For $b,b'\in B$ the product $bb'$ lies in $\mathcal{M}$, and a given $m$ is a product $bb'$ in at most $\tau(m)$ ways, so $S\ge(\sum_{b\in B}1/b)^2$. If $E$ is a set of primes and $p\notin E$, every $b\le T$ prime to $E$ is uniquely $p^k b'$ with $b'$ prime to $E\cup\{p\}$, so the sum of $1/b$ over the $b\le T$ prime to $E$ is at most $p/(p-1)$ times the same sum for $E\cup\{p\}$. Adding the prime factors of $h$ one at a time gives

As $T+1>y^{1/4}=X^{1/20}$, we get $S\ge(\log X)^2/(400G(h)^2)$, that is, $X/S\le400G(h)^2X/(\log X)^2$. Finally, if $n<X$ and $n,n+h$ are prime, then $n\le z$ or $(n(n+h),P)=1$, so the count is at most $z+1+X/S+y^3\le400G(h)^2X/(\log X)^2+3X^{3/5}$.

(ii) For $t=p-1\ge1$, $(t+1)^5\le(t+31)t^4$, that is, $(p/(p-1))^4\le1+30/p$. Hence $G(h)^4\le\sum_{d}30^{\omega(d)}/d$ over the squarefree $d\mid h$, and

Proof of Theorem 4.1. Let $S=\sum_{n\le N}f(n)e(n\alpha)$, $L=\log N$ and $\ell=\lfloor\log_2N\rfloor$. Since $N\ge rR\ge4$, $L\ge1$. If $\ell<64$, then $L<64\log2<45$ and $|S|\le N\le45N/L$. Let $\ell\ge64$, $I=\lfloor\log_2\ell\rfloor+1$ and $J=\ell+1-4I$. Then $16^I>\ell^4$, $1\le J\le\ell\le2L$, $I\le\ell\le2L$, $2I\le2\ell$, $N<2^{\ell+1}=2^J2^{4I}$ and $J^22^J\le(\ell+1)2^{2\ell+1}\ell^{-4}\le2N$. By Lemma 4.4, $|S|L\le C_5N+|T_1|+|T_2|$, where $T_1$ and $T_2$ are the parts of $\sum_p\log p f(p)\sum_{m\le N/p}f(m)e(pm\alpha)$ with $p\le2^J$ and with $p>2^J$.

The small primes. Let $0\le j<J$, $U=2^j$, $H=\lfloor N/U\rfloor$, and for $U<x\le2U$ let $B(x)=\sum_{m\le H,\;xm\le N}f(m)e(xm\alpha)$; the inner sum for a prime $p\in(U,2U]$ is $B(p)$. By Cauchy’s inequality, Lemma 4.3(ii), (iii) and Lemma 4.2(iii) with $M=U$, $K=j$,

where $Q_j = H(U + 2(4H/r + 1)(3U + 4r + 8rj))$. Since $HU \le N$, $UQ_j \le7NU + (8 + 16j)Nr + 24N^2/r + (32 + 64j)N^2/U$, and $\log(2U) \le j + 1$. Summing over $j < J$ with $j+1 \le J$,

and $\sum_{j\ge0}(j+1)^2(3/4)^j = 112$,

Now $J^22^J \le2N$ gives $3\sqrt{7J}\sqrt{N2^J} \le12N$; $r \ge R \ge\sqrt{R}$ gives $\sqrt{24/r} \le5R^{-1/4}$; and $r\sqrt{R} \le rR \le N$ gives $\sqrt{24JNr} \le5JNR^{-1/4}$. With $J \le2L$ and $L \ge1$, $|T_1| \le908N + 60L^3NR^{-1/4}$.

The large primes. For $p > 2^J$ we have $N/p < 16^I$, so the $m$ in $T_2$ lie in $(0,16^I-1]$, the union of the blocks $(16^i-1,16^{i+1}-1]$ with $0 \le i < I$. Fix $i$, let $A = 16^i-1$, $U = 15\cdot16^i$ and $X = \lfloor N/16^i\rfloor$, and assume $X \ge1$, the block being empty otherwise. Only the primes $p \in(2^J,X]$ contribute, since $p \ge X+1$ and $m \ge16^i$ give $pm > N$. Let $V$ be the set of these primes, which are odd, and $B(m) = \sum_{\substack{p\in V,\,pm\le N}}\log p\, f(p)e(pm\alpha)$. The block is $\sum_{A<m\le A+U} f(m)B(m)$, and by Cauchy’s inequality, Lemma 4.3(ii) and $\log p \le\lambda= \log(X+1)$, its square is at most $U\lambda^2W$, where

The count vanishes for odd $h$, and for even $h$ Lemma 4.5(i), applied to $X+1$, bounds it by $400G(h)(X+1)\lambda^{-2} + 3(X+1)^{3/5}$. By Cauchy’s inequality, Lemma 4.5(ii) and Lemma 4.2(iii), $\sum_{h\le X}G(h)^2w_U(h\alpha) \le e^{15}\sqrt{X}Q^{1/2}$ with $Q = (4X/r + 1)(20rU + 3U^2)$, and $\sum_{h\le X}w_U(h\alpha) \le XU$. Hence $U\lambda^2W \le A_1 + 800e^{15}Z + A_3$, where

Let $\kappa= \log(N+1) \ge\lambda$ and $T_i = 4^i\kappa\bigl(N(2N)^{3/5}\bigr)^{1/2}$. Since $U^2X = 225\cdot16^i(16^iX) \le225\cdot16^iN$ and $X+1 \le2N$, we get $A_1 \le225T_i^2$ and $A_3 \le1350T_i^2 \le37^2T_i^2$. With $w = UX \le15N$, $X \le N/16^i$ and $R \le r \le N/R$,

and every coefficient is at most $40^4$, so $Z^{1/2} \le40(N2^{-i} + 2NR^{-1/4} + 2^iN^{3/4})$. The block is therefore at most

with $K_b = 80\sqrt{800e^{15}} + 52$. Summing over $i < I$,

Here $I \le2L^3$; $2^I \le4L \le16N^{1/4}$; $4^I \le16L^2$ and $\kappa\le2L$; and $\log x \le15x^{1/15}$ gives $L^3\left(N(2N)^{3/5}\right)^{1/2} \le2\cdot15^3N$. Hence $|T_2| \le K_b(216018N + 2L^3NR^{-1/4})$.

Altogether $|S|L \le(C_5 + 908 + 216018K_b)N + (60 + 2K_b)L^3NR^{-1/4}$, and dividing by $L$ gives the theorem with $C_1 = 45 + C_5 + 908 + 216018K_b + 60 + 2K_b$. □

Proof of Theorem 1.1

In this section $\chi$ is a primitive character modulo $q \ge3$.

Proof. We may take $x=T$ to be an integer. Let $\tau=\sum_{a\bmod q}\overline{\chi}(a)e(a/q)$. Since $\overline{\chi}$ is primitive, $\sum_a\overline{\chi}(a)e(an/q)=\chi(n)\tau$ for every $n$, and summing the squares of the moduli of these identities over $n$ mod $q$ gives $q\varphi(q)=|\tau|^2\varphi(q)$, so $|\tau|=\sqrt q$. Summing over $1\le n\le T$,

where $a$ runs over the integers with $-q/2<a\le q/2$, $a\ne0$. For $0<|\theta|\le1/2$ put $r(\theta)=(1-e(-\theta))^{-1}-(2\pi i\theta)^{-1}$; then $|1-e(-\theta)|=2|\sin\pi\theta|\ge4|\theta|$. If $2\pi|\theta|\le1$, then $|e(-\theta)-1+2\pi i\theta|\le(2\pi\theta)^2$ and $|r(\theta)|\le(2\pi\theta)^2/(4|\theta|\cdot2\pi|\theta|)<3$; otherwise $|r(\theta)|\le1/(4|\theta|)+1/(2\pi|\theta|)<3$. The terms with $r(a/q)$ contribute at most $6q$. Writing $a=\pm m$ with $1\le m\le q/2$, the remaining terms are $q/(2\pi i)$ times a combination, with coefficients of modulus at most $1$, of four sums $\sum_{m\le H}\overline{\chi}(m)e(m\beta)/m$ with $H\le q/2$, so they contribute at most $2qB/\pi$. Dividing by $|\tau|$ gives the claim. □

Proof. Every $n\leq t$ with $P(n)>Y$ is uniquely $n=pm$ with $p=P(n)$ prime, $Y<p\leq t/m$ and $P(m)\leq p$, and then $m\leq t/Y$. For such $p$ we have $p>r$, so $p\nmid r$, and on the units modulo $r$ the function $u\mapsto e(umb/r)$ equals $\sum_\psi c_\psi\psi(u)$, the sum over the characters $\psi$ modulo $r$, with $|c_\psi|\leq1$.

The character $\chi\psi$ modulo $qr$ is nonprincipal. Otherwise $\chi(n)=\overline{\psi}(n)$ for every $n$ prime to $qr$. Let $d=(q,r)$ and let $n$ be prime to $q$ with $n\equiv1\pmod d$. By the Chinese remainder theorem there is $n'$ prime to $qr$ with $n'\equiv n\pmod q$ and $n'\equiv1\pmod r$, and then $\chi(n)=\chi(n')=\overline{\psi}(n')=1$. So $\chi$ is trivial on the units congruent to $1$ modulo $d$, and is induced by a character modulo $d\leq r<q$, which contradicts primitivity.

Applying (2) to $\xi=\chi\psi$ with $\gamma=m\beta$, $A=\max(Y,P(m)-1)$ and $B=\lfloor t/m\rfloor$ (the inner sum is empty if $A\geq B$) gives

and $\sum_{m\leq M}m^{-19/20}\leq20M^{1/20}$. Hence $C_2=40C_3$ will do. □

Proof. Let $L=\log q$, $M=\lceil L\rceil$, $R=M^{16}$ and $Y=M^{700}$. Since $e^{L/16}\geq(L/16)^4/24>L+1\geq M$, we have $2\leq R<q$ and $R\leq Y$. Split the sum according to $P(m)\leq Y$ or $P(m)>Y$. By Lemma 5.2 the first part is at most $e^{11}\log Y$. For the second put $A(t)=\sum_{\substack{n\leq t\\P(n)>Y}}\chi(n)e(n\beta)$ and $w(t)=1/t-1/(t+1)$. Partial summation and $|A(H)|\leq H$ give

If $t\leq Y$, then $A(t)=0$. Let $t>Y$ and $Q=\lfloor t/R\rfloor\geq1$. By Dirichlet’s theorem there are coprime $a,r$ with $1\leq r\leq Q$ and $|\beta-a/r|\leq1/(r(Q+1))$; then $|\beta-a/r|t\leq R$ (Figure 3). If $r\leq R$, then Lemma 5.3 with $b=a$ gives $|A(t)|\leq C_2kt$, where

If $r>R$, then $R\le r\le t/R$ and $\lvert\beta-a/r\rvert\le r^{-2}$, so Theorem 4.1 for $f=\chi$ bounds the full sum $\sum_{n<t}\chi(n)e(n\beta)$, and since $\log t\le L$, removing the $\Psi(t)=\#\{n\le t:P(n)\le Y\}$ smooth terms gives

Since $tw(t)\le1/t$ and $w(t)\le1/t^2$,

The first sum is at most $3+\log L$, the second at most $1+L$, and by partial summation the third is at most $\sum_{n\le H,\ P(n)\le Y}1/n\le e^{11}\log Y$. Finally $L\le M\le2L$ gives $\rho(1+L)\le2/M\le1$; $\log(qR+2)\le18M$, $2+2\pi R\le8M^{16}$, $Y^{1/20}=M^{35}$ and $\log Y=700\log M\ge700$ give $k(1+L)\le288M^{34}/(700M^{35})\le1$; and $\log Y=700\log M\le1400\log L$. Collecting terms, the sum is at most $1+4C_1+C_2+(2800e^{11}+C_1)\log L\le(2800e^{11}+1+5C_1+C_2)\log L$. □

Proof of Theorem 1.1. The character $\overline{\chi}$ is primitive modulo $q$. If $\log q\ge200$, then Proposition 5.4 for $\overline{\chi}$ and Lemma 5.1 give

If $\log q < 200$, then every sum $\sum_{m\le H}\overline{\chi}(m)e(m\beta)/m$ with $H\le q$ has modulus at most $1+\log q<201$, and Lemma 5.1 gives

The logarithmic derivative at $s=1$

Recall that $\sigma_0=7/8+3/1000$ and that $K$ is the constant of Corollary 3.8.

Proof. By Lemma 3.1(i) with $a=\chi\Lambda$, for real $s>1$,

As $s\to1^+$ the left side tends to $\int_1^\infty S(\chi;t)t^{-2}\,dt$ by dominated convergence, since $|S(\chi;t)|\le Kt^{\sigma_0}\log(q+2)$ and $\sigma_0<1$. The function $L(s,\chi)$ is entire and does not vanish at $s=1$ by Theorem 1.2, so the right side tends to $-\frac{1}{2}\frac{L'}{L}(1,\chi)$. $\square$

Proof of Theorem 1.3(i). Let $\chi$ be nonprincipal modulo $q$, so $q\ge3$, and put

Since $|S(\chi;t)|\le\psi(t)\le4t$ by Lemma 2.1(ii), Lemma 6.1 gives

As $q+2\le q^2$, $\log\log(q+2)\le\log2+\log\log q$, and since $\log\log q\ge\log\log3>0$ the right side is at most $C\log\log q$. $\square$

For the lower bound in Theorem 1.3(ii) we need to control the prime powers $n\le q^{17}$ with $n\equiv1\pmod q$. We count them in dyadic blocks with Selberg’s sieve.

Proof. If $1+mq=p^k$ with $p\le z$, then $p^k\in(Mq,2Mq)$, and for each prime $p$ at most one power of $p$ lies in this interval, since $p^{k+1}\ge2p^k$. These $m$ number at most $z$. If $p>z$, then $1+mq$ has no prime factor up to $z$, and we apply Lemma 2.2 to the $M$ integers $a_m=1+mq$, $M\le m<2M$, with $P$ the product of the primes up to $z$, $\nu(d) = 1/d$ and $y = z$. Every prime $p \le z$ differs from $q$, so for $d \mid P$ the condition $d \mid1 + mq$ fixes $m$ in one residue class modulo $d$, and $\lvert R_d\rvert\le1$. Here $g(l) = \prod_{p\mid l}(p-1)^{-1}$, which is the sum of $1/n$ over the $n$ whose set of prime factors is that of $l$. Every $n \le\sqrt{z}$ has all its prime factors at most $z$ and the product of its distinct prime factors is at most $\sqrt{z}$, so

For squarefree $d$, $3^{\omega(d)} = \tau_3(d)$, and $\sum_{d\le z} \tau_3(d) = \#\{(a,b,c):abc\le z\} \le z\left(\sum_{a\le z}\frac{1}{a}\right)^2 \le z(1+\log z)^2$. Lemma 2.2 therefore bounds the number of these $m$ by $2M/\log z+z(1+\log z)^2$.

Proof. Write $n=1+mq$ with $1\le m<q^{16}$, and let $J=\lfloor16\log_2 q\rfloor+1$, so that $2^J>q^{16}$ and $J\le25\log q$. We split the range of $m$ into the blocks $2^j\le m<2^{j+1}$, $0\le j<J$ (Figure 4), and let $N_j$ be the number of $m$ in the $j$-th block with $1+mq$ a prime power. We claim $N_j\le393\cdot2^j/(j+1)$. For $j<32$ this holds trivially. For $j\ge32$ apply Lemma 6.2 with $M=2^j$ and $z=2^u$, $u=j/32\ge1$. Since $2^j<2^J\le2q^{16}$, we have $z<2^{1/32}q^{1/2}<q$. Then $2M/\log z=64\cdot2^j/(j\log2)\le96\cdot2^j/(j+1)$, and since $\log z\le u$,

because $(2+u)^2(32u+1)\le9u^2\cdot33u=297u^3$ and $u^3\le2^{3u}$. This proves the claim.

A term of the $j$-th block has $\Lambda(n)\le\log(1+2^{j+1}q)\le(j+2)\log2+\log q$ and $n>2^jq$, so the block contributes at most

Summing over $j<J$ and using $\sum_{j<J}1/(j+1)\le1+\log J$, $J\le25\log q$ and $\log J\le4+\log\log q$, the sum in the lemma is at most $\frac{393}{q}(35\log q+5\log q+\log q\log\log q)$. Since $\log\log q\ge\log\log3>1/11$, this is at most $C_0\log q\log\log q/q$ with $C_0=393\cdot441$.

Proof of Theorem 1.3(ii). Let $q \ge3$ be prime and put $c(n)=\sum_{\chi\ne\chi_0}\chi(n)$, the sum over the nonprincipal characters modulo $q$. By orthogonality $c(n)=(q-1)1[n\equiv1\pmod q]-1[q\nmid n]$. Put

By Lemma 6.1, $\sum_{\chi\ne\chi_0}\frac{L'}{L}(1,\chi)=-2I$, so by (1) it suffices to show $-C\log q\le I\le C\log q\log\log q$.

By Corollary 3.8(i), $|T(t)|\le qK\log(q+2)t^{\sigma_0}$. Let $Y=q^{17}$. Since $17(\sigma_0-1)<-2$ and $\log(q+2)\le q$,

For the lower bound, $c(n)\ge-1$ gives $-T(t)\le\psi(t)\le4t$, so

For the upper bound, $c(n)\le(q-1)1[n\equiv1\pmod q]$ gives

which is at most $\frac{C_0}{2} \log q \log\log q$ by Lemma 6.3. Hence

and both bounds follow since $\log q > 1$ and $\log\log q > 1/11$. □

Data availability

Deep Bhattacharjee computed the Lean formalisation and the Julia, C, C++, shell and Python computations with the help of AI assistance (Claude, Anthropic). The Lean formalisation of the proofs in this paper is archived at Zenodo, doi:10.5281/zenodo.23383716. The paper is available at https://github.com/creelie/Breakthrough-problems-3/blob/main/preprintPolyaVinogradovLogLog/PolyaVinogradovLogLog.pdf.

Competing interests

None.

Funding

None.

Formerly, Electro-Gravitational Space Propulsion Laboratory (EGSPL), Bhubaneswar, Odisha 751030, India

Email address: [email protected]

Email address: [email protected]

URL: https://orcid.org/0000-0003-0466-750X

Formerly, National Taiwan University, Taipei 106319, Taiwan

Email address: [email protected]

URL: https://orcid.org/0009-0002-2254-3914