On a Class of Sums with Unexpectedly High Cancellation, and its Applications
Ernie Croot Hamed Mousavi





Department of Mathematics, Georgia Tech, Atlanta, US.


On a class of sums with unexpectedly high
cancellation, and its applications
    Ernie Croot, Hamed Mousavi
    July 2019
============================================================================




Following attempts at an analytic proof of the Pentagonal Number
Theorem, we report on the discovery of a general principle leading to
an unexpected cancellation of oscillating sums, of which ∑_n^2≤ x(-1)^ne^√(x-n^2)
is an example (to get the idea of the result). It turns out that sums in the
class we consider are much smaller than would be predicted by certain
probabilistic heuristics. After stating the motivation, and our theorem,
we apply it to prove several results on the Prouhet-Tarry-Escott Problem, integer partitions, and the distribution
of prime numbers. Regarding the Prouhet-Tarry-Escott problem, for example, we show that

    ∑_|ℓ|≤ x(4x^2-4ℓ^2)^2r-∑_|ℓ|<x(4x^2-(2ℓ+1)^2)^2r=polynomial w.r.t.  x  with degree 2r-1.

Note that the degree is unexpectedly small. This can perhaps be proved using properties of Bernoulli polynomials, but the claim fell out of our method in a more natural and motivated way. Using this result, we solve an approximate version of the Prouhet-Tarry-Escott Problem, and in doing so we give some evidence that a certain pigeonhole argument for solving the exact version of the Problem can be improved. In fact, our work in the approximate case exceeds the bounds one can prove using a pigeonhole argument, which seems remarkable. Also, we prove
that

    ∑_ℓ^2 < n (-1)^ℓ p(n-ℓ^2) ∼ (-1)^n 2^-3/4 n^-1/4√(p(n)),

where p(n) is the usual partition function.
We get the following “Weak pentagonal number theorem", in which we can replace the partition function p(n) with Chebyshev Ψ function:

    ∑_0 < ℓ < √(xT)/2Ψ([e^√(x - (2ℓ)^2/T),e^√(x - (2ℓ-1)^2/T)]) =Ψ(e^√(x))(1/2 +
    O (e^-0.196√(x))),



where T=e^0.786√(x),
where Ψ([a,b]) := ∑_n∈ [a,b]Λ(n) and
Ψ(x) = Ψ([1,x]), where Λ is the von
Mangoldt function. It is possible to extend this to a range of values of T, with a more complicated error term. Note that this last equation (sum over ℓ) is
stronger than one would
get using a strong form of the Prime Number Theorem and also a naive use of the Riemann
Hypothesis in each interval,
since the widths of the intervals are smaller than e^1/2√(x), making the Riemann Hypothesis estimate “trivial".














§ INTRODUCTION


In this paper, we use the notation f(x)≃ g(x), which means that there exists C>0 such that

    lim sup_x→∞|f(x)|/|g(x)|=C;

In particular, we show f∼ g if C=1. We sometimes need to use big Oh notation f(x)=O(g(x)), which means that

    lim sup_x→∞|f(x)|/|g(x)| <∞.

Also we say f(x) = o(g(x)) if

    lim inf_x→∞|f(x)|/|g(x)| =0 .

and f(x) = ω(g(x)) if g(x) = o(f(x)). Finally we may like to emphasize that the constants in these notations are functions of specific variable like y. In that case we write them like ≃_y, ≪_y, O_y(f(x)), ...



The partition function p(n) is the number of ways to represent n as sum of positive non-decreasing integers.
The Pentagonal Number Theorem of Euler asserts that for an integer x≥ 2,

    ∑_G_n≤ x(-1)^np(x-G_n)=0

where G_n=n(3n-1)/2 is the nth pentagonal number. Various proofs of this theorem have been developed over the
decades and centuries - see <cit.>; but we wondered whether it was possible to produce an “analytic proof", using the Ramanujan-Hardy-Rademacher formula - see <cit.> - for p(x):

    p(n)=1/2π√(2)∑_k=1^∞(√(k)(∑_0≤ h<k
    (h,k)=1ω(h,k)e^-2π ihn/k)d/dx(sinh(π/k√(2/3(x-1/24)))/√(x-1/24))|_x=n),

where ω(h,k) is a sum over some roots of unity. Considering just the first two terms in this formula, one sees that (see <cit.>)

    p(x)=p_2(x)+O(√(p(x))),   where   p_2(x)=√(12)e^π/6√(24x-1)/24x-1(1-6/π√(24x-1)).

So, the Pentagonal Number Theorem implies

    ∑_G_n≤ x(-1)^np_2(x-G_n)≪√(xp(x));

In fact, one can get a better bound by using more terms in the Ramanujan-Hardy-Rademacher expression; one might call this a “Weak Pentagonal Number Theorem", which is an
interesting and non-trivial bound for the size of this oscillating sum of
exponential functions (-1)^np_2(x-G_n).
It is worth pointing out that this bound is much smaller than what
would be expected on probabilistic grounds: if we consider a sum

    S(X_1,X_2,⋯)=∑_G_n<xX_np_2(x-G_n),

where the X_ns are independent random variables taking the values +1
and -1, each with probability 1/2, then E(S^2)=∑_G_n≤ xp_2(x-G_n)^2. So the quality of bound we would expect to prove is

    |S|≪(∑_G_n≤ xp_2(x-G_n)^2)^1/2≪√(x) p(x),

However, the bound (<ref>) is much smaller than the RHS here.



What we have discovered is that (<ref>) is just the tip of the iceberg, and
that there is a very general class of sums like this that are small - much
smaller than one would guess based on a probabilistic heuristic. Roughly,
we will prove that

    ∑_f(n)≤ x (-1)^n e^c√(x-f(n))=“small",


where f is a quadratic polynomial (with positive leading coefficient), and c is some constant. It is possible to produce a more general class of sums with a lot of cancellation; and we leave it to the reader to explore. As a consequence of this and the Ramanujan-Hardy-Rademacher
expansion for p(n), we will prove that

    ∑_l^2<n(-1)^l p(n-l^2) ∼ (-1)^n √(p(n))/2^3/4 n^1/4.

As another category of results, we will also prove a corollary of Theorem <ref> related to prime numbers. In fact let x>0 be large enough and


T=e^0.786√(x).

Then

    ∑_0 ≤ℓ < 1/2√(xT)Ψ([e^√(x - (2ℓ)^2/T),e^√(x - (2ℓ-1)^2/T)]) =Ψ(e^√(x))(1/2 +
    O (e^-0.196√(x))).

Finally we will develop polynomial identities that occur naturally in the Taylor expansion in (<ref>). For example

    ∑_|ℓ|≤ x(4x^2-4ℓ^2)^2r-∑_|ℓ|<x(4x^2-(2ℓ+1)^2)^2r=polynomial w.r.t.  x  with degree 2r-1.






Many of the results stated above can be deduced from the following:







Let b,d∈ℝ, a,c>0;
Also, let h(x) be a polynomial with no 

real pole p_0 with |p_0|<x^1/2-ϵ. 

Then

    ∑_n:an^2+bn+d<x(-1)^n e^c√(x-(an^2+bn+d))h(n)≪ e^(w+ϵ)c√(x).

where w>0 is defined as follows. Set

    Δ:=sup_r≥ 0√(√(a)r√(ar^2+4)+r√(a)/2)-π r/c.

Then w=min(1,Δ).










Obviously forcing w to be less than or equal to one is to avoid getting a trivial result, and if a,c,r are chosen in such a way that sup_r Δ(r)>1,
then this theorem becomes useless.











Observing the numerical results suggest that

    ∑_ℓ^2<x(-1)^ℓ e^√(x-ℓ^2)=e^o(√(x)).







There is another generalization when we pick a complex c in (<ref>). In this case, having an upper bound for the sum is harder, as we have both the fast growth of exponential functions and the extra oscillation coming from the imaginary exponent.







For large enough x>0, let T:=T(x) be at least ω(x^2) as x→∞. Also let α+iβ∈ℂ and 0≤α<1+ϵ for a fixed ϵ>0, and |β|<√(T). Then for arbitrary δ>0

    ∑_l^2<Tx(-1)^l e^(α+iβ)√(x-l^2/T)≪√(Tx/|β|+1)e^α(√(1/1+π^2)+δ)√(x)+√(T).








Note that if β=0 and T sufficiently large, theorem <ref> becomes a special case of theorem <ref> for a=1, b,d=0, and c→ 0 with a weaker result.

Even these theorems do not exhaust all the cancellation types of oscillatory sums of this
form, for we can replace the square-root by a fourth-
root, and then replace the quadratic polynomial with a quartic. We will
not bother to develop the most general theorem possible here.
Next, we prove three applications for these oscillation sums.















 §.§ Applications to the Chebyshev Ψ function


We show that in the “Weak pentagonal number theorem" we can replace the partition function p(n) with Chebyshev Ψ function.







Assume ϵ>0, x is large enough and T=e^4/3(1-1/√(1+π^2))√(x), then 

we have

    ∑_|ℓ|<√(Tx)(-1)^ℓΨ(e^√(x-ℓ^2/T))≪ e^(2/3+1/3√(1+π^2)+ϵ)√(x):= e^w√(x).








We give an argument to show a relation between the theorem and the distribution of prime numbers. A weak version of theorem can be written as

    Ψ(e^√(x))=2∑_0<ℓ<√(xT)/2(Ψ(e^√(x-(2ℓ -1)^2/T))-Ψ(e^√(x-(2ℓ)^2/T)))+O(e^(7/9+ϵ)√(x))   where  T:= e^8√(x)/9.




Consider the following set of intervals:

    I:= ⋃_0<ℓ<√(xT)/2(e^√(x-(2ℓ)^2/T),e^√(x-(2ℓ-1)^2/T))

One can see that the measure of I is almost half of the length of the interval [0,e^√(x)]. Roughly speaking theorem <ref> states that the number of primes in I, with weight log(p), is half of the number of primes, with the same weight. This prime counting gives a stronger result than one would
get using a strong form of the Prime Number Theorem and also the Riemann
Hypothesis(RH), where one naively estimates the Ψ function on each of the
intervals. Because the widths of the intervals are smaller than e^√(x)/2, making the Riemann Hypothesis estimate “trivial". However, a less naive argument can give an improvement like corollary <ref>. See Table <ref> for comparison.
















Assuming RH and the same notation as in theorem <ref>

    ∑_|ℓ|<√(xT)(-1)^ℓΨ(e^√(x-ℓ^2/T))≲ e^(1/3+1/6√(1+π^2))√(x)≲ e^0.38√(x).






The proof needs careful computations of a cancellation sum involving zeroes of the Riemann zeta function. In fact, we use our cancellation formula to control the low-height zeroes; The Van der Corput bound for exponential sums combined with the Montgomery Mean-value theorem to control the high-height zeroes.






Note that numerical results up to x<300 show a very smaller error term in comparison to (<ref>). In particular, for example,

    |∑_l<2400(-1)^lΨ(e^√(300-l^2/T))| < 100    where T∼ 20000.











A more applicable identity may be one having with fewer terms (with lower frequency) in (<ref>). We can choose the parameters to get

    ∑_l^2<xe^2ϵ√(x)(-1)^lΨ(e^√(x-l^2e^-2ϵ√(x)))≲ x^2e^(1-ϵ)√(x).

This identity does not give the same level of cancellation as RH anymore but still is better than the best cancellation one can get from the current unconditional estimates for Ψ function. Also, the advantage is that the intervals (e^√(x-(2ℓ)^2ϵ√(x)),e^√(x-(2ℓ-1)^2ϵ√(x))) are not as small as what we had in (<ref>). So it possibly is more suitable for combinatorial applications.













 §.§ Applications to the usual and restricted partitions

A generalization of the Pentagonal Number Theorem is the second application of the cancellation result. It is an interesting question to find the second dominant term of general,“Meinardus type" integer partitions. Our result is applicable in general if the second term of Meinardus's Theorem is known. But the known asymptotic formulas rely heavily on analytic properties of the parts. For many partition functions λ(n), we see a formula like 

    λ(n)∼(g(n))^qe^(k(n))^θ(1-1/(h(n))^r)+O(λ(n)^s)

where 0<s<1 and θ,r,q>0 and k(n) is a linear polynomial and g(n),h(n) are rational functions. For example for the usual partition function we have 
    g(n)=√(12)/24n-1   ,  
    h(n)=π^2/36(24n-1)   ,   
    k(n)=π^2/36(24n-1)    ,  
    s=θ=q/2=r=1/2

Assuming a partition function has form (<ref>), we can conclude that for a quadratic polynomial t(n)=an^2+bn+d as stated in theorem <ref>  we have

    ∑_ℓ: t(ℓ)<n(-1)^l λ(n-t(ℓ)) ≪λ^κ(n)

where κ=max(w,s) and w is defined as in Theorem <ref>, and s in (<ref>). As long as κ<1, we can get a nontrivial approximation of the Pentagonal Number Theorem. We will verify this inequality for some polynomials and give a few specific examples.





First, we mention a weak pentagonal number theorem for certain approximations of the partition function.




Let

    p_1(x)   =e^π√(2x/3)/4x√(3)
    
    p_2(x)   =(√(12)/24x-1-6√(12)/π(24x-1)^3/2)e^π/6√(24x-1)
    
    p_3(x)   =(√(6)(-1)^x/24x-1-12√(6)(-1)^x/π(24x-1)^3/2)e^π/12√(24x-1)

be the asymptotic approximation of partition function, the contribution for k=1, and the contribution for k=2 in  the Ramanujan-Hardy-Rademacher formula (<ref>), respectively. Then

    ∑_G_l<x(-1)^lp_1(x-G_l)≪ p(x)^0.31
       ∑_G_l<x(-1)^lp_2(x-G_l)≪ p(x)^0.21
       ∑_G_l<x(-1)^l√(p_1(x-G_l))≪ p(x)^0.13
       ∑_l^2<xp_3(x-l^2)≪ p(x)^0.11






We mentioned  (<ref>) here because they have very small error terms.

Equation (<ref>) gives us a very promising perspective to possibly prove the pentagonal number theorem using an analytic argument. We will state a possible future direction after giving its proof.


Note that equation (<ref>) does not have the factor (-1)^l, because ∑_h ω(h,2) in equation (<ref>) is (-1)^l/√(2). So it can cancels out the other (-1)^l from the weak pentagonal number theorem to eliminate the cancellation. In fact, if we put (-1)^l, we get the following proposition.









For large enough integer x


    ∑_l^2<x(-1)^lp_3(x-l^2)∼e^π ix√(p(x))/√(8x).

So if p_4(x)=p_2(x)+p_3(x) is the first “four" terms in the Ramanujan-Hardy-Rademacher expression for the partition function, then we get

    ∑_l^2<x(-1)^lp_4(x-l^2)∼√(p(x))/√(8x),

which immediately implies (<ref>).








We mention another set of examples. It is reported in <cit.> that p(n;α, M) the number of partitions with parts of the form Mt±α, 1≤α≤ M-1, and (α,M)=1 is

    p(n;α, M)=π(πα/M)/√(12Mn-6α^2+6Mα-M^2)
    I_1(π√(12Mn-6α^2+6Mα-M^2)/3M)+O(e^π√(n)/√(3M)).

Theorem <ref> can show a weak pentagonal number expression like

    ∑_am^2+bm+d<x(-1)^m p(x-am^2-bm-d;α, M)≃“small function w.r.t. x,α, a ,M".

where I_1 is the modified Bessel function of the first kind.  We take two cases M=2 and M=5 as examples. It is known that number of partitions into distinct parts, see <cit.>, is

    q(n):= Ad/dx(I_0(π√(2x+1/12/3)))|_x=n+O(√(q(n))).

where A is a constant and I_0 is Bessel function.






Let q_1(n) be the first two terms in the expansion of q(n). For large n

    ∑_l^2≤ n(-1)^l q_1(n-l^2)   ≪ q(n)^0.151
    ∑_l^2≤ n(-1)^l q(n-l^2)   ≪√(q(n)).








Also for M=5, see <cit.>, there exists a constant A:=A_a>0 and a constant B>0 such that

    p(n;a,5)∼Bπ(π a/5)/(60n-A)^3/4
    e^π√(60n-A)/15








Let h(n) be the main contribution  in the expansion of p(n;a,5). For large n

    ∑_l^2≤ n(-1)^l h(n-l^2)≪ p(n;a,5)^0.13
       ∑_ℓ^2≤ n(-1)^ℓ p(n-ℓ^2;a,5)≪√(p(n;a,5)).























 §.§ Applications to the Prouhet-Tarry-Escott Problem


Another application of our method involves the so-called Prouhet-Tarry-Escott Problem. The problem is to determine, for a fixed integer n ≥ 1,
the largest value k (denote by M(n)) with k ≤ n-1 for which there exist two sequences of n
integers a_1, ⋯, a_n and b_1,⋯, b_n, say - such that for all 1≤ r≤ k we have (see <cit.>)

    ∑_i=1^na_i^r=   ∑_i=1^nb_i^r 
    ∑_i=1^na_i^k+1≠   ∑_i=1^nb_i^k+1 and multi-sets {a_i},{b_i}.




One could consider a weakening of this problem, where the left and right
hand sides of (<ref>) are merely required to be “close to each other". One way to naturally view this approximation is to interpret {a_i},{b_i} to be values taken on by two  discrete uniform random variables A,B that takes on rational values and both of whose moments (up to a certain level) and their moment generating functions are “close"; i.e. the probability density function of these random variables becomes almost the same.
Approximating moment generating functions is an important problem in the literature - see for example <cit.>; and what we are interested in is that the probability space is a subset of ℚ. This makes the problem non-trivial.



This problem can be also viewed from another perspective that is related to the Vingradov mean value theorem. Consider J_n,k(N) to be the number of solutions in equations (<ref>) and remove the restriction a_i≠ b_j and assume that 1≤ a_i,b_i≤ N. It was conjectured that

    J_n,k(N) ≪_ϵ N^ϵ(N^n + N^2n - 1/2k(k+1)).

Note that there are N^n trivial solutions in this setting. This conjecture has been proved for k=3 by Wooley at <cit.> and was proved for k≥ 4 at <cit.> by Bourgain, Demeter, and Guth. Note that this view is closely related to Waring's problem. For more information about this direction, please check the survey paper <cit.>. 








Let us formulate the problem as follows.

Let 0 < c = c(N,n,k) < 1 be the smallest constant such that there
exist sequences of integers

    1≤ a_1≤ a_2≤⋯≤ a_n≤ N    and    1≤ b_1≤ b_2≤⋯≤ b_n≤ N

that do not overlap  and  for all 1≤ r≤ k,

    |∑_i=1^na_i^r-b_i^r|≤ N^cr

How small can we take c to be for various ranges of k and n?







There has been little progress in solving the original PTE problem. For example for an ideal solution (when k=n-1) the largest known solution is for n=12, see <cit.>. To our knowledge, the best constructive solution is perhaps for the range k=O(log(n)). Using a pigeonhole argument we can do much better, and give non-constructive solutions with k as large as k ∼ c √(n). In section <ref> we will briefly explain this argument, which gives one of the best known non-constructive ways to solve the problem <ref>.

Note that using the Vingradov conjecture (<ref>), the trivial upper bound becomes sharper when k>2√(n) (the right hand side becomes N^n+ϵ). So we expect to have harder time finding a nontrivial solution.
Even applying the pigeonhole argument to the approximate version (Problem <ref>) we cannot make k much larger; for example, we cannot prove the existence of non-decreasing sequences a_i and b_i such that


    |∑_i a_i^r - b_i^r| < N^r(1-1/log n)   for all    1 ≤ r ≤√(n)(log n)^2.


In other word, one cannot guarantee that the value of c in Problem <ref> can be c < 1 - 1/log n when k > √(n)(log n)^2. We will see that this range for c is much, much weaker than what our construction gives. This suggests that it might be possible to beat the bounds that the pigeonhole principle gives for the exact version of the problem.
 We will give a proof to the following theorem, which states a constructive solution for problem <ref> when k is much bigger than √(n).







Equation (<ref>) has a constructive solution for c∼13/28  and k ∼n^6/7/log(n) as follows. For 1≤ i≤√(N)

    a_i = N-(2i-2)^2∈ℕ   and   
    b_i=N-(2i-1)^2∈ℕ .

Then for all 1≤ r≤ k∼ N^3/7 we have

    ∑_1≤ i≤ na_i^r-∑_1≤ i≤ n b_i^r≪ r^r/2 N^r+1/4≪ N^r+1/4+ rlog(r)/2log(N).





In fact we prove a more general theorem In section <ref> as follows.






Let L≥ 1 and m∈ℕ and define M=⌊ (2L)^2m/2m+1⌋. Define for 1≤ i≤ n:=L^m

    a_i=M^2m+1-(2i-2)^2   ,
    b_i=M^2m+1-(2i-1)^2    , 1≤ r≤ k≪_m M^m/log(M).

Then

    ∑_1≤ i≤ La_i^r-∑_1≤ i≤ L b_i^r≪ r^r/2+ϵM^(2m+1)r/4+m≪ r^r/2+ϵ a_1^r+1/4.

So we have two sets of around n integers less than N:=M^2m+1, and they are satisfying the equation (<ref>) with c∼1/2-1/4m+2+ϵ and k ≃ n^1-1/m.


















There is a conjecture in <cit.> stating that if {a_n≥ 0},{b_n≥ 0} be an ideal solution of Prouhet-Tarry-Escott problem and a_1<b_1, then for all i

    (a_i-b_i)(a_i+1-b_i+1)<0.

Although our example cannot resolve the conjecture, it shows that equation (<ref>) is not true for the solutions of Problem <ref> for any c.










Note that we can win by a constant factor - i.e. increase M(n) by a constant, if we pick a suitable quadratic polynomial q(l) instead of l^2.






Lastly, we investigate the problem more concretely by viewing a_i,b_i as polynomials. Then this cancellation sum can be considered as an operator in ℤ[x] which cuts the degree to half.






Let M ∈ℕ, and define f_r(M) := ∑_|ℓ| < 2M (-1)^ℓ (4M^2 - ℓ^2)^r; Then, f_r(M) is a polynomial of degree r-1 in M when r is even, and is a polynomial of degree r in M when r is odd; that is, when r is even,

    f_r(M) = c_0(r) + c_1(r) M + ⋯ + c_r-1(r) M^r-1,

where c_0(r),...,c_r-1(r) are integer functions of r only (and not of M). The same general form holds for r odd, except that the degree here is r, not r-1. Furthermore, under the assumption r ≪M/log(M) we have that all the coefficients have size O(r^r+ϵ).

















§ PROOF OF THE OSCILLATION SUMS


In this section we mainly prove theorems <ref> and <ref>. First, we mention a lemma.





Let z= A+iB be a complex number and q(s)=as^2+bs+c be a quadratic polynomial and x∈ℝ. Then

    Re(√(x-q(z)))= √(1/2(√(D^2+(2aAB + bB)^2) +D))
    Im(√(x-q(z)))= √(1/2(√(D^2+(2aAB + bB)^2) -D)).

where

    D := x - (A^2-B^2)a - bA -c.








We only prove (<ref>).

We have

    x-q(z) = x-(A^2-B^2)a-bA-c - i (2ABa+bB).

It impliess that

    Re(√(x-q(z)))= √(D^2+(2aAB + bB)^2)cos(1/2tan^-1(2aAB + bB/D)).

Noting that cos^2(y)=1+cos(2y)/2 and cos(arctan(y))=1/√(1+y^2)

    Re(√(x-q(z))) = √(D^2+(2aAB + bB)^2)√(1/2 + 1/2√(1+(2aAB + bB)^2/D^2)).

Straightforward computation results in equation (<ref>).









Next, we prove Theorem <ref>.

Let q(z):=az^2+bz+d and f(z)=√(x-q(z)) with branch points α_1,α_2.

We choose (-∞,α_1]∪ [α_2,∞) as the branch cut and let G be the interior of the square with vertices

    ±(√(x/a)-2b/a)± iu√(x),

where u>0 will be chosen later. Note that 
    α_2>√(x/a)-2b/a

and we have a similar condition for α_1. Without loss of generality we assume that h is holomorphic inside G.











Let
g(z)=e^c f(z), which is analytic inside G. Define

    H(z)=g(z)h(z)/sin(π z).

Assume that γ is the boundary of G (see figure <ref>). Using the residue theorem

    ∫_γH(z)dz=2π i ∑_z_j: polesRes(H(z))|_z_j=2π i∑_q(n)<x(-1)^nh(n)e^c√(x-q(n)).

We wish to show that the integral in LHS has size of at most e^cw√(x). First assume that we choose z∈γ_1∪γ_3. So z=t± iu√(x) for -√(x/a)+2b/a<t<√(x/a)-2b/a. If t=o(√(x)), then √(x-az^2-bz-d)∼√(x(1+au^2)). Otherwise by lemma <ref>

    Re(√(x-az^2-bz-d))≪√(√((x-at^2+au^2x)^2+4a^2t^2u^2x)+x+au^2x-at^2/2)

A straightforward computation shows that the maximum of RHS of (<ref>) is at t=o(√(x)). So

    Re(√(x-az^2-bx-d))≤√(x(1+au^2)).

As c>0, we conclude in both cases that
e^c√(x-az^2-bz-d)≪ e^c√(x(1+au^2)).
Also we have |sin(π z)|∼1/2e^π u√(x).
So we will get that for z∈γ_1,γ_3

    |H(z)|≪ e^c√(x(1+au^2))-π u√(x)

We desire to make the contribution from z∈γ_1,γ_3 to be approximately equal to the contribution from z∈γ_2,γ_4. It means that we need c√(x(1+au^2))-π u√(x)<wc√(x), where w is defined in the theorem. We need to express u in terms of w. 
After solving this we get two cases. If π^2≠ ac^2, then

    -cwπ+c√(π^2-ac^2+ac^2w^2)/π^2-ac^2<u.

Otherwise, we will get

    c(1-w^2)/2π w<u.


Now we compute the case z∈γ_2,γ_4. We have z=±√(x/a)∓2b/a+it and -u√(x)<t<u√(x). If t=o(√(x)), then √(x-q(z))=o(√(x)). Otherwise, using lemma <ref>

    Re(√(x-q(z)))≪√(t√(a)√(at^2+4x)+t√(a)/2).

Let t=r√(x). We need to choose a proper α as follows.

    α=argmax_r(c√(r√(a)√(ar^2+4)+r√(a)/2)-π r)    ,   0≤ r≤ u.

Also we assume that ±√(x/a)∓2b/a is far enough from integers (otherwise we shift the legs γ_2,γ_4 slightly to avoid Re(z) being near to integer). So we conclude that |sin(π rz)|>λ >0 for a fixed λ. Then we have

    ∫_γ_2,γ_4e^c√(x-q(z))h(z)/sin(π z)≪√(x)e^c√(xα√(a)√(aα^2+4)+α√(a)/2)-πα√(x) h(√(x))

Finally in order to satisfy (<ref>) and (<ref>) and the fact that u≥ r, we choose

    u=max(-cwπ+c√(π^2-ac^2+ac^2w^2)/π^2-ac^2, α)  or   u=max(c(1-w^2)/2π w
    ,α).

where

    w=√(α√(a)√(aα^2+4)+α√(a)/2)-πα/c.









In this paper, we need two versions of the Van der Corput lemma.
The versions we give here are a little different than what is known in <cit.>. But these versions are straightforward and enough for the purpose of this paper.








[Simpler version] Let F(x) be a second differentiable function in (a,b); also 0<M<|F'(x)|, and |G(x)|<R for x∈ (a,b). Assume that G(x)/F'(x) is a piecewise monotone function. Then

    ∫_a^be^iF(x)G(x)dx≪R/M.










<cit.>

 

Suppose that f(x) is a real-valued function such that 0<λ_2≤ f”(x) for all x∈ [a,b], and suppose that |f^(3)(x)|≤λ_3 and that |f^(4)(x)|≤λ_4 throughout this interval. Put f'(a)=α, f'(b)=θ. For integers ν∈ [α-1,θ+1] let x_ν be the root of the equation f'(x)=ν. Then

    ∑_a≤ n≤ be^2π if(n)=e^π i/4∑_α-1≤ν≤θ+1e^2π i(f(x_ν)-ν x_ν)/√(f”(x_ν))   +O(log(4+θ-α)) +O(λ_2^-1/2(θ-α+2))
    
       +O((λ_3^2λ_2^-3+λ_4λ_2^-2)(b-a)(θ-α+2)).




Note that if f”(x)<-λ_2<0, then e^π i/4 will change e^-π i/4.










Proof of Theorem <ref>. 

Let T>0 and γ be the contour with vertices

    ±√(η xT)± iu√(x)

where η=π^2/1+π^2-ϵ and  0<u will be determined later (see figure <ref>).
Let

    h_T(z)=e^(α+iβ)√(x-z^2/T)/sin(π z)














We take the branch cut to be (-∞,-√(xT)]∪ [√(xT),∞). The Residue Theorem implies

    ∫_γh_T(z)dz=2π i∑_ℓ^2<Txη(-1)^ℓ e^(α+iβ)√(x-ℓ^2/T).

Now we compute the case where z∈γ_1,γ_3. So z=t± iu√(x) and -√(Txη)<t<√(Txη). As x≪√(T) we have

    √(x-z^2/T)
    =√(x-t^2-u^2x± 2iut√(x)/T)∼√(x+-t^2∓ 2iut√(x)/T+O(1/√(T)))

If t√(x)=o(√(T)), then noting x-t^2/T=x+o(1/x) we conclude that

    √(x-z^2/T)∼√(x) + C(x,T)+iB(x,T), where B(x,T)=o(1/√(T))  and C(x,T)=o(1/x).

Otherwise, recall that in the worst case, t∼√(xT). We use lemma <ref> to get

    √(x-z^2/T)   ∼√(√((x-t^2/T)^2+4u^2t^2x/T^2)+(x-t^2/T)/2)+i√(√((x-t^2/T)^2+4u^2t^2x/T^2)-(x-t^2/T)/2)

Because of the range of values of t, x-t^2/T≥ (1-η)x.
So

    √((x-t^2/T)^2+4u^2t^2x/T^2)-(x-t^2/T)= 4u^2t^2x/T^2/√((x-t^2/T)^2+4u^2t^2x/T^2)+(x-t^2/T)≤2u^2t^2/(1-η)T^2.

Therefore in all cases for t

    Re(√(x-z^2/T))   ≤√(x)  and  
    Im(√(x-z^2/T))
    ≤√(xu^2η/(1-η)T).

Noting that |β|≤√(T)

    Re((α+iβ)√(x-z^2/T))
    ≤α√(x)+√(xu^2η/(1-η))|β|/√(T)≤√(x)(α+u√(η/(1-η)))

So for z∈γ_1,γ_3 we have

    e^(α+iβ)√(x-z^2/T)/sin(π z)≪ e^(α+u√(η/(1-η))-π u)√(x).

We will later choose proper w,η,u such that

    α+u√(η/(1-η))-π u + log(T)/2√(x)<w.

Next we assume that z∈γ_2,γ_4.
We have z=±√(η xT)+it and -u√(x)≤ t≤ u√(x).
As t≪√(x)≪√(T), then t√(x)/√(T)≪ 1 and t^2/T≪x/T=o(1). We use lemma <ref> to conclude that

    √(x-z^2/T)   ∼√(x/T)(√(√(4t^2η+xT(1-η)^2)+(1-η)√(xT)/2)+i√(√(4t^2η+xT(1-η)^2)-(1-η)√(xT)/2))
                                               ∼√((1-η)x)+it√(η/T(1-η)).

This together with the fact that |β|<√(T) imply that

    Re((α+iβ)√(x-z^2/T))
    ≤α√((1-η)x)+|β|/√(T)√(η t^2/1-η)≤α√((1-η)x)+|t|√(η/1-η)

Again we assume that √(xTη) is far away from the integers; so as sin(π z)>λ>0 for some fixed λ, therefore for z∈γ_2,γ_4

    e^(α+iβ)√(x-z^2/T)/sin(π z)≪ e^α√((1-η)x)+|t|(√(η/1-η)-π).

As √(η/1-η)<π, the maximum of the following function occurs at y=0:

    G(y)=α√((1-η))+y√(η/1-η)-yπ.

We conclude that

    2π i∑_ℓ^2<Txη(-1)^ℓ   e^(α+iβ)√(x-ℓ^2/T)=∫_γh_T(z)dz
       ≪√(Tx)e^(α+u√(η/(1-η))-π u)√(x) + √(x)e^α√((1-η))√(x).

A straightforward calculation shows that

    |∑_xTη≤ℓ^2<Tx(-1)^le^(α+iβ)√(x-ℓ^2/T)|≪∑_xTη≤ℓ^2<Txe^α√(x-ℓ^2/T)≪√(xT)e^α√(x(1-η)).

For a sharper bound, we use lemma <ref> to control the tail. Without loss of generality assume that β<0. We prove that for |β|≪√(T), 

    |∑_xTη≤ℓ^2<Tx-T(-1)^ℓ e^iβ√(x-ℓ^2/T)|≪√(Tx^3/2)/√(|β|+1)+  √(Tx^11)/|β|+1+log x .

It is trivial to get the bound for |β|<1, so we assume otherwise. Let f(ℓ):=1/2ℓ+β/2π(x-ℓ^2/T)^1/2. Then 

    f'(ℓ)    = 1/2 -βℓ/2π T(x-ℓ^2/T)^-1/2
               f”(ℓ) = -β x/2π T(x-ℓ^2/T)^-3/2
    
        f^(3)(ℓ)    = -3β xℓ/2π T^2(x-ℓ^2/T)^-5/2
               f^(4)(ℓ) = -3β x/2π T^2(x+4ℓ^2/T)(x-ℓ^2/T)^-7/2.

First we evaluate f' at the endpoints. Without loss of generality we consider √(xTη)<ℓ<√(xT-T). Assuming that η<0.9, we have

    f'(√(xTη))    = 1/2 - β√(xη)/2π√(T)(x-η x)^-1/2∈ [0,1]
    
        f'(√(xT-T))    = 1/2 - β√(xT-T)/2π T <√(x).

As f”,f^(3),f^(4),f^(5) are positive, we can find λ_2,λ_3,λ_4 easily at the endpoints. 

    λ_2    = inf_√(Txη)<ℓ<√(xT-T) f”(ℓ) = f”(√(xTη)) = |β| /2π  T√(x)(1-η)^3/2≫|β|/T√(x)
    λ_3    =sup_√(Txη)<ℓ<√(xT-T) f^(3)(ℓ) = f^(3)(√(xT-T)) = -3β x/2π T^2(xT-T)^1/2≪|β|x^3/2/T^3/2
    λ_4    =sup_√(Txη)<ℓ<√(xT-T) f^(4)(ℓ) = f^(4)(√(xT-T)) = -3β x/2π T^2(5x-4)≪|β|x^2/T^2.

It implies that

    λ_3^2λ_2^-3+λ_4λ_2^-2≪x^9/2/|β|+1.

Noting that f'(√(xT-T))-f'(√(xTη)) =O(√(x)) and applying lemma <ref> implies the equation (<ref>).





For xTη<t^2<xT-T  we define

    S(t):=∑_xTη≤ℓ^2<t^2(-1)^ℓ e^iβ√(x-ℓ^2/T).
 
Similar to what we just did, we know that |S(t)|≪ x^5t/√(|β|)≪√(x^11T/|β|) for xTη<t^2<xT-T. Using Abel's summation formula we get

    |∑_xTη≤ℓ^2<Tx-T   (-1)^ℓ e^(α+iβ)√(x-ℓ^2/T)|
       ≪ |S(√(xT-T))|e^α+|S(√(η xT))|e^α√((1-η)x)+|∫_√(η xT)^√(xT-T)S(t)v(t)dt|

where v(t):= d/dtexp(α√(x-t^2/T)). We bound the integral in the RHS.

    ∫_√(η xT)^√(xT-T)S(t)v(t)dt    = -α/T∫_√(η xT)^√(xT-T)tS(t) e^α√(x-t^2/T)/√(x-t^2/T)dt.

 Straightforward computation  gives that

    G(t):= tS(t) e^α√(x-t^2/T)/√(x-t^2/T)   ≪(√(Tx^3/2)/√(|β|+1)+ log x + √(Tx^11)/|β|+1)e^α√((1-η)x)√(xT)






It implies that

    |∫_√(η xT)^√(xT-T)S(t)v(t)dt |   ≪√(xT)/T(√(Tx^3/2)/√(|β|+1)+ log x + √(Tx^11)/|β|+1)e^α√((1-η)x)√(xT)
       ≪(√(Tx^5/2)/√(|β|+1)+√(x)log x + √(Tx^12)/|β|+1)e^α√((1-η)x).

This, (<ref>), and (<ref>) give

    |∑_xTη≤ℓ^2<Tx-T   (-1)^ℓ e^(α+iβ)√(x-ℓ^2/T)|≪(√(Tx^5/2)/√(|β|+1)+√(x)log x + √(Tx^12)/|β|+1)e^α√((1-η)x).

Considering the range of β in our application, we conclude that

    |∑_xTη≤ℓ^2<Tx(-1)^ℓ e^(α+iβ)√(x-ℓ^2/T)|   ≤|∑_xTη≤ℓ^2<Tx-T(-1)^ℓ e^(α+iβ)√(x-ℓ^2/T)|+|∑_xT-T≤ℓ^2<Tx(-1)^ℓ e^(α+iβ)√(x-ℓ^2/T)|
       ≪√(x^3T/|β|+1) e^α√((1-η)x) + √(Tx).

We used a trivial bound for the second sum. We want to have

    |∑_ℓ^2<Tx(-1)^ℓ e^(α+iβ)√(x-ℓ^2/T)|≪√(T/|β|+1)e^w√(x).

Adding (<ref>) and (<ref>) we need to have 

    α√(1-η)≤ w
    α+u√(η/(1-η))-π u + 1/2√(x)log(|β|+1)≤ w.

Remember that η=π^2/1+π^2-ϵ. Comparing with β, if we choose u large enough  then the left hand side of the second condition in (<ref>) becomes negative. So

    w=α√(1/1+π^2)+ϵ

from the first condition.
This completes the proof.


















§ PROOF RELATED TO PRIME DISTRIBUTION




Inspired by the proof of the Prime Number Theorem (PNT) we compute the following sum in two ways.

    1/2π i∑_ℓ^2<Tx(-1)^ℓ∫_1+ϵ-i√(T)^1+ϵ+i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds.

In this section, we assume that T<e^4/3√(x). 








For large enough x

    ∑_ℓ^2<Tx   (-1)^ℓ∫_1+ϵ-i√(T)^1+ϵ+i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds≪√(Tx)e^(1/√(1+π^2)+ϵ)√(x).












We consider the contour γ in figure <ref>, where ϵ>0 is a very small real number and U is a very large real number far enough from any negative even integer -2m. Using the Residue Theorem

    ∑_ℓ^2<Tx   (-1)^ℓ∫_γζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds
       =2π i∑_ℓ^2<Tx(-1)^ℓ((lim_s→ 0e^s√(x-ℓ^2/T)(ζ'(s)/ζ(s)))+e^√(x-ℓ^2/T)
                         +∑_|Im(ρ_m)|<√(T)e^ρ_m√(x-ℓ^2/T)/ρ_m-∑_1≤ m≤ U/2e^-2m√(x-ℓ^2/T)/2m),

where ρ_m is the m^th non trivial zeroes of the Rieman zeta function. 











An easy computation shows that the first and fourth terms in the RHS sum have contribution at most √(Tx). Using Theorem <ref> (by tending c→ 0) the second term is bounded from above  by √(Tx)e^ϵ√(x) .
We can use Theorem <ref> to show that 

    ∑_ℓ^2<Tx(-1)^ℓ e^ρ_m√(x-ℓ^2/T)≪√(Tx/|Im(ρ_m)|+1)e^(1/√(1+π^2)+ϵ)√(x).
 Finally, using the fact that 

    ∑_|Im(ρ_m)|<√(T)1/Im(ρ_m)^3/2
 
converges, we can conclude that the third term of RHS of (<ref>) has contribution at most √(Tx)e^(1/√(1+π^2)+ϵ)√(x). So we have

    ∑_ℓ^2<Tx   (-1)^ℓ∫_γζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds≪√(Tx)e^(1/√(1+π^2)+ϵ)√(x).

As e^s√(x-ℓ^2/T)/s tends to zero for Re(s)→ -∞, we can pick U large enough to have 

    ∑_ℓ^2<Tx(-1)^ℓ∫_γζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds ≃   ∑_ℓ^2<Tx(-1)^ℓ∫_1+ϵ-i√(T)^1+ϵ+i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds
       +∑_ℓ^2<Tx(-1)^ℓ∫_-U-i√(T)^1+ϵ-i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds
       +∑_ℓ^2<Tx(-1)^ℓ∫_1+ϵ+i√(T)^-U+i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds.

The second integral in the RHS is

    |∑_ℓ^2<Tx   (-1)^ℓ∫_-U-i√(T)^1+ϵ-i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds|
       =|∑_ℓ^2<Tx(-1)^ℓ∫_-U-i√(T)^-i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds+∫_-i√(T)^1+ϵ-i√(T)ζ'(s)/ζ(s)∑_ℓ^2<Tx(-1)^ℓ e^s√(x-ℓ^2/T)/sds|
       ≪√(Tx)∫_-∞^0|ζ'(σ-i√(T))/ζ(σ-i√(T))|e^σ√(x)/√(T)dσ+1/√(T)∫_0^1+ϵ|ζ'(s)/ζ(s)|√(Tx^2)e^σ(1/√(1+π^2)+ϵ)√(x)dσ.

Note that in the last inequality we used Theorem <ref>. We can use the fact that ζ'/ζ(σ+it)=∑_ρ1/σ+it-ρ+O(log(t)) to choose a proper T such that ζ'/ζ(σ± i√(T))≪log^2(T) for -∞≤σ<1+ϵ. So we have

    ∑_ℓ^2<Tx   (-1)^ℓ∫_-U-i√(T)^1+ϵ-i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds
       ≪√(x)log^2(T)+√(x)/√(T)∫_0^1+ϵ|ζ'(σ-i√(T))/ζ(σ-i√(T))| e^σ(1/√(1+π^2)+ϵ)√(x)dσ
       ≪log^2(T)/√(T)e^(1+ϵ)√(x/1+π^2).

The third integral can be similarly bounded. This, (<ref>), and (<ref>) give the result.












Proof of Theorem <ref>. 
We compute (<ref>) another way. We have

    ∑_ℓ^2<Tx(-1)^ℓ   ∫_1+ϵ-i√(T)^1+ϵ+i√(T)ζ'(s)/ζ(s)e^s√(x-ℓ^2/T)/sds=∑_ℓ^2<Tx(-1)^ℓ∫_1+ϵ-i√(T)^1+ϵ+i√(T)∑_n=1^∞Λ(n)/n^se^s√(x-ℓ^2/T)/sds
    
    =   ∑_ℓ^2<Tx(-1)^ℓ(∑_1≤ n≤ e^√(x-ℓ^2/T)+∑_e^√(x-ℓ^2/T)≤ n∫_1+ϵ-i√(T)^1+ϵ+i√(T)Λ(n)/n^se^s√(x-ℓ^2/T)/sds):=A_1+A_2

First we compute A_1.
Again, we use the contour γ in figure <ref> to compute the integral. Knowing |e^√(x-l^2/T)/n|>1, we conclude that the integrand is tending to zero as Re(s)→ -∞. Considering sufficiently large  U and Using the Residue Theorem give 

    A_1≃   ∑_ℓ^2<Tx(-1)^ℓ∑_1≤ n≤ e^√(x-ℓ^2/T)Λ(n)∫_γ(e^√(x-ℓ^2/T)/n)^sds/s
       +∑_ℓ^2<Tx(-1)^ℓ∑_1≤ n≤ e^√(x-ℓ^2/T)Λ(n)∫_-U+i√(T)^1+ϵ+i√(T)(e^√(x-ℓ^2/T)/n)^sds/s
       -∑_ℓ^2<Tx(-1)^ℓ∑_1≤ n≤ e^√(x-ℓ^2/T)Λ(n)∫_-U-i√(T)^1+ϵ-i√(T)(e^√(x-ℓ^2/T)/n)^sds/s
    
    =   2π i∑_ℓ^2<Tx(-1)^ℓΨ(e^√(x-l^2/T))
    + ∑_ℓ^2<Tx(-1)^ℓ∑_n≤ e^√(x-ℓ^2/T)Λ(n)∫_-U+ i√(T)^1+ϵ+ i√(T)(e^√(x-ℓ^2/T)/n)^sds/s
                      -∑_ℓ^2<Tx(-1)^ℓ∑_n≤ e^√(x-ℓ^2/T)Λ(n)∫_-U- i√(T)^1+ϵ- i√(T)(e^√(x-ℓ^2/T)/n)^sds/s.

We  bound the integrals in RHS. Define 

    y_n(V):=Λ(n) ∫_-U± iV^1+ϵ± iV∑_ℓ^2<Tx-Tlog^2(n)(-1)^ℓ(e^√(x-ℓ^2/T)/n)^sds/s

Inspired by  <cit.> there exists  √(T)<V<2√(T) such that

    ∑_n≤ e^√(x)   |y_n(V)|= ∑_n≤ e^√(x)(y_n(V)y_n(V))^1/2
       =∑_n≤ e^√(x)(Λ(n)^2|∫_-U± iV^1+ϵ± iV∑_ℓ^2<Tx-Tlog^2(n)(-1)^ℓ(e^√(x-ℓ^2/T)/n)^sds/s|^2)^1/2
       ≪∑_n≤ e^√(x)Λ(n)(1/√(T)∫_√(T)^2√(T)∫_-U^1+ϵ|∑_ℓ^2<Tx-Tlog^2(n)(-1)^ℓ(e^√(x-ℓ^2/T)/n)^σ+it|^2dσ/σ^2+t^2 dt)^1/2
       ≪∑_n≤ e^√(x)Λ(n)/√(T)(∫_-U^1+ϵ∑_ℓ_1^2<ℓ_2^2<T(x-log^2(n))e^σ(√(x-ℓ_1^2/T)+√(x-ℓ_2^2/T))/n^2σ|∫_√(T)^2√(T)e^it(√(x-ℓ_1^2/T)-√(x-ℓ_2^2/T))dt/σ^2+t^2| dσ)^1/2
           +∑_n≤ e^√(x)Λ(n)/√(T)(∑_ℓ^2<T(x-log^2(n))∫_-U^1+ϵe^2σ√(x-ℓ^2/T)/n^2σ∫_√(T)^2√(T)dt/σ^2+t^2 dσ)^1/2.

We use Lemma <ref> for G(t):=1/σ^2+t^2 and F(t):=t(√(x-ℓ_1^2/T)-√(x-ℓ_2^2/T)) (i.e.  F'(t)≥ℓ_2^2-ℓ_1^2/2T√(x)) for the off-diagonal terms in the last expression of RHS in (<ref>). Note that we could get the same result without using the lemma, but this way is more straightforward. Then 

    ∑_n≤ e^√(x)|y_n(V)|   ≪√(x)/√(T)∑_n≤ e^√(x)Λ(n)(∑_ℓ_1^2<ℓ_2^2<T(x-log^2(n))∫_-U^1+ϵe^σ(√(x-ℓ_1^2/T)+√(x-ℓ_2^2/T))/n^2σ(ℓ_2^2-ℓ_1^2) dσ)^1/2
       +1/√(T)∑_n≤ e^√(x)Λ(n)(∑_ℓ^2<T(x-log^2(n))e^2(1+ϵ)√(x-ℓ^2/T)/n^2(1+ϵ))^1/2
       ≪(∑_m<√(Tx)τ(m)/m)^1/2√(x)e^(1+ϵ)√(x)/√(T)∑_n≤ e^√(x)Λ(n)/n^1+ϵ+√(x)e^(1+ϵ)√(x)/√(T)∑_n≤ e^√(x)Λ(n)/n^1+ϵ

where τ(m) is the number of divisors of m. So there exists  √(T)< V<2√(T) we have

    ∑_n≤ e^√(x)Λ(n)   ∫_-U± iV^1+ϵ± iV∑_ℓ^2<T(x-log^2(n))(-1)^ℓ(e^√(x-ℓ^2/T)/n)^sds/s≪∑_n≤ e^√(x)|y_n(V)|
    ≪x^1/4e^(1+ϵ)√(x)log T/√(T).

This and (<ref>) imply that 

    A_1=2π i∑_l^2<Tx(-1)^l Ψ(e^√(x-l^2/T))+O(x^1/4e^(1+ϵ)√(x)/√(T)).












Next we compute A_2. We consider contour γ' in Figure <ref>. As e^s√(x-l^2/T)/sn^s does not have poles inside γ', choosing large enough U and  using the Cauchy's integral theorem give

    A_2≃∑_ℓ^2<Tx(-1)^l(∑_e^√(x-ℓ^2/T)≤ n∫_1+ϵ+ i√(T)^U+ i√(T)Λ(n)/n^se^s√(x-ℓ^2/T)/sds-∑_e^√(x-ℓ^2/T)≤ n∫_1+ϵ- i√(T)^U- i√(T)Λ(n)/n^se^s√(x-ℓ^2/T)/sds).

Similar to y_n, we define z_n as follows: 

    z_n(V) := Λ(n)∑_T(x-log^2(n))<ℓ^2<Tx(-1)^ℓ∫_1+ϵ± iV^U± iVe^s√(x-ℓ^2/T)/sn^sds

 In this case, we will have

    ∑_n|z_n(V)|
    
    
       =∑_n<e^√(x)Λ(n)|∑_T(x-log^2(n))<ℓ^2<Tx(-1)^ℓ∫_1+ϵ± iV^U± iVe^s√(x-ℓ^2/T)/sn^sds|
       +∑_e^√(x)<nΛ(n)|∑_ℓ^2<Tx(-1)^ℓ∫_1+ϵ± iV^U± iVe^s√(x-ℓ^2/T)/sn^sds|.

As these cases are similar, we only compute the bound for the case e^√(x)<n. There exists √(T)<V<2√(T) such that

    ∑_e^√(x)<n   |z_n(V)|≪1/√(T)∑_e^√(x)<nΛ(n)(∫_√(T)^2√(T)∫_1+ϵ^U|∑_ℓ^2<Tx(-1)^ℓ e^s√(x-ℓ^2/T)|^2 dσ/n^2σ(σ^2+t^2) dt)^1/2
       ≪1/√(T)∑_e^√(x)<nΛ(n)(∫_1+ϵ^U1/n^2σ∑_ℓ_1^2<ℓ_2^2<Tx e^σ(√(x-ℓ_1^2/T)+√(x-ℓ_2^2/T))∫_√(T)^2√(T)e^it(√(x-ℓ_1^2/T)-√(x-ℓ_2^2/T))/(σ^2+t^2) dtdσ)^1/2
       + 1/√(T)∑_e^√(x)<nΛ(n)(∫_√(T)^2√(T)∫_1+ϵ^U|∑_ℓ^2<Tx(-1)^ℓ e^s√(x-ℓ^2/T)|^2 dσ/n^2σ(σ^2+t^2) dt)^1/2
       ≪1/√(T)∑_e^√(x)<nΛ(n)(∫_1+ϵ^U1/n^2σ∑_ℓ_1^2<ℓ_2^2<Tx e^σ(√(x-ℓ_1^2/T)+√(x-ℓ_2^2/T))∫_√(T)^2√(T)e^it(√(x-ℓ_1^2/T)-√(x-ℓ_2^2/T))/(σ^2+t^2) dtdσ)^1/2
                   +1/√(T)∑_e^√(x)<nΛ(n)(∫_√(T)^2√(T)∑_ℓ^2<Tx∫_1+ϵ^Ue^2σ√(x-ℓ^2/T)/n^2σdσ/(σ^2+t^2) dt)^1/2.

Let F(t)=t(√(x-ℓ_1^2/T)-√(x-ℓ_2^2/T)) and G(t)=1/(σ^2+t^2). Then we conclude that |F'(t)|≫ℓ_2^2-ℓ_1^2/T√(x) and |G(t)|≪1/(σ^2+T).
Using lemma <ref>

    ∑_e^√(x)<n|z_n(V)| ≪√(x)/√(T)   ∑_e^√(x)<nΛ(n)(∑_ℓ_1^2<ℓ_2^2<Tx1/ℓ_2^2-ℓ_1^2∫_1+ϵ^Ue^σ(√(x-ℓ_1^2/T)+√(x-ℓ_2^2/T))/n^2σdσ)^1/2
       +√(x)/√(T)∑_e^√(x)<nΛ(n)e^(1+ϵ)√(x)/n^1+ϵ
    ≪√(x)/√(T)   ∑_e^√(x)<nΛ(n)e^(1+ϵ)√(x)/n^1+ϵ(∑_m<Txτ(m)/m)^1/2
       +√(x)/√(T)∑_e^√(x)<nΛ(n)e^(1+ϵ)√(x)/n^1+ϵ≪√(x)log(T)e^(1+ϵ)√(x)/√(T).

So there exists √(T)<V<2√(T) such that 

    A_2≪∑_e^√(x)≤ n|z_n(V)|≪√(x)log(T)e^(1+ϵ)√(x)/√(T).

Putting  (<ref>) and (<ref>) into (<ref>) and comparing it with (<ref>) gives

    ∑_ℓ^2<Tx(-1)^l Ψ(e^√(x-ℓ^2/T))≪√(Tx)e^(1+ϵ)√(x/1+π^2)+x^3/4/√(T)e^(1+ϵ)√(x).

Taking T=e^4(1+ϵ)/3√(x)(1-√(1/1+π^2)) gives the desired result.















§ PROOF RELATED TO THE PENTAGONAL NUMBER THEOREM. 

We start this section by proving the weak pentagonal number theorem for truncation of the usual partition function. 







We start with the proof of proposition <ref>.







For (<ref>) we only need to put c=π√(2/3), a=3/2, b=-1/2, d=0 in theorem <ref>; for equation (<ref>), pick c=π/√(6), a=3/2, b=-1/2, d=0 and use Theorem <ref>; and for equation (<ref>) we need to pick c=π/√(6) and a=1, and b=d=0. 

We prove equation (<ref>).
Let f(z)=π√(24(x-z(3z-1)/2)-1/36) and b^2=1/12. 
We choose the branch cut (-∞,α_1]∪ [α_2,∞). Then let G be the interior of the square with vertices (see figure <ref>)
 
    ±√(2x/3)∓ 1± ib√(x),


Define 

    h(z) :=e^ f(z)/sin^3(π z) =e^π√(24(x-z(3z-1)/2)-1/36)/sin^3(π z).

Using the residue theorem 

    ∫_γ   h(z)dz=2π i ·∑_z_i: poles Res(h(z_i))

We compute the residues of h(z). We know that for z near to ℓ∈ℤ we have

    1/(sin(π z))^3 = (-1)^ℓ/π^3(z-ℓ)^3 +(-1)^ℓ/2π (z-ℓ)+⋯
       e^f(z) = e^f(ℓ) + f'(ℓ)e^f(ℓ)(z-ℓ) + (f'(ℓ))^2+f”(ℓ)/2e^f(ℓ)(z-ℓ)^2+⋯

Also 

    ( f(z))' = π (1-6z)(24(x-z(3z-1)/2)-1)^-1/2
    ( f(z))” = -144π x (24(x-z(3z-1)/2)-1)^-3/2

So we have

    Res  h(z)|_z=ℓ   = (-1)^ℓe^ f(ℓ)(1/2π+(f'(ℓ))^2+f”(ℓ)/2π^3)
       = (-1)^ℓe^ f(ℓ)/2π(24(x-G_ℓ)-1)(24(x-G_ℓ)-1+(1-6ℓ)^2-144x/π√(24(x-G_ℓ)-1))
       =(-1)^ℓe^ f(ℓ)/2π(24(x-G_ℓ)-1)(24x-144x/π√(24(x-G_ℓ)-1))

It implies that

    ∫_γh(z)dz   =24ix∑_G_l<x(-1)^le^π/6√(24(x-G_l)-1)/(24(x-G_l)-1)(1-6/π√(24(x-G_l)-1))
       =24ix/√(12)∑_G_l<x(-1)^lp_2(x-G_l).

We bound the integral. First assume that we choose z∈γ_1∪γ_3. So z=t± ib√(x) for -√(2x/3)+1<t<√(2x/3)-1. For large enough x we have

    24(x-z(3z-1)/2)-1/36∼2/3x-t^2+b^2x∓ 2ibt√(x).

Similar to the proof of theorem <ref> for z∈γ_1,γ_3

    e^π√(24(x-z(3z-1)/2)-1/36)≤ e^π√(2x/3+b^2x).

Also |sin^3(π z)| ∼1/8e^3π b√(x), and considering b^2=1/12 we get that

    π(√(2/3+b^2)-3b) = 0.

So the contribution of the horizontal legs is at most o(x). Now we compute the case z∈γ_2,γ_4. We have z=±√(2/3x)∓ 1+it and -b√(x)<t<b√(x). We have

    24(x-z(3z-1)/2)-1/36
    =2/3x-2/3×2x∓ 2it√(6x)-3t^2∓ 7it -(2√(6)+√(2/3))√(x)+4/2-2/3

If t=o(√(x)), then 24(x-z(3z-1)/2)-1/36=o(x). Otherwise, since √(x),t are negligible in comparison to x,t^2

    24(x-z(3z-1)/2)-1/36∼ t^2∓ it√(8x/3).
 
Using lemma <ref> we have

    Re(√(24(x-z(3z-1)/2)-1/36))
    
       ≤√(t/2√(3)(√(3t^2+8x)+t√(3)))

Hence in any case we get

    |e^π√(24(x-z(3z-1)/2)-1/36)/(sin (π z))^3|≪ e^π√(t/2√(3)(√(3t^2+8)+t√(3)))-3π t.



Maximizing for t in the RHS of (<ref>), we get that the integral in the LHS of (<ref>) can be at most e^0.21√(x). 
It completes the proof.





Perhaps the upper bound in equation  (<ref>) becomes smaller by taking higher powers of sin(π z). However, this argument needs a new nontrivial input to construct the proof of the Pentagonal Number Theorem. In other word, one may take the function

    H(z) := ∑_k∈ℤ∑_0≤ h<k
    (h,k)=1sinh(π/6√(24(x-z(3z-1)/2)-1))y(x,z,h,k)/(sin(π z))^2r+1

for suitable function y(x,z,h,k) and integer r to generate all of the terms in the Ramanujan-Hardy-Rademacher formula (<ref>) for the partition function. One may use this possible nontrivial observation to  prove that all of the error terms from different k,h will cancel each other, which is equivalent to the Pentagonal Number Theorem.








Proof of Proposition <ref>.  We have

    ∑_ℓ^2<x   (-1)^ℓ p_3(x-ℓ^2)=√(6)e^π i x∑_ℓ^2<x(1/24(x-ℓ^2)-1-12/π(24(x-ℓ^2)-1)^3/2)e^π/12√(24(x-ℓ^2)-1)
       =√(6)e^π/12√(24x-1)+π i x∑_ℓ^2<x/4e^-2πℓ^2/√(24x-1)(√(1-24ℓ^2/24x-1)+1)(1/24(x-ℓ^2)-1+O(1/√(x^3)))
       ∼ e^π/12√(24x - 1) + π i x/4x √(6)∑_ℓ^2 < √(x)ln x e^-ℓ^2/2σ^2,

where 

    σ^2 = √(6x)π.

The last expression in the above can be approximated as follows

    1/4 x √(6)e^π/12√(24x - 1) + π i x∑_ℓ^2 < √(x)ln x e^-ℓ^2/2σ^2    ∼    1/4x √(6) e^π/12√(24x-1) + π i x∫_-∞^∞ e^-t^2/2σ^2 dt
       =    σ√(2π)/4x√(6) e^π/12√(24x-1) + π i x
       ∼    e^π ix 2^3/4x^1/4√(p(x)).










We need the next lemma. 




With the same notation as theorem <ref>

    ∑_n:an^2+bn+d<x(-1)^n I_α(c√(x-an^2+bn+d))h(n)=O(e^cw√(x)).

where I_α is the Bessel function.








Before we mention the proof note that for fixed α and large enough x

    I_α(x) ∼e^x/√(2π x)(1 + O(1/x)).
 




Since the proof is very similar to proof of <ref>, we skip the details. Let H(z)=h(z)I_α(√(x-z^2))/sin(π z) and q(n)=an^2+bn+d and assume the contour γ in <ref>. Then

    ∑_ℓ: q(ℓ)<x(-1)^ℓ I_α(c√(x-q(ℓ)))h(ℓ)=∫_γH(z)dz

For z∈γ_1,γ_3 

    |H(z)|≪I_α(c√(x(1+au^2)))/e^π u√(x)≪ e^c√(x(1+au^2))-π u√(x).

Also for z∈γ_2,γ_4

    |H(z)|≪ I_α(c√(ux/2(√(au^2+4)+u√(a))))≪√(x)e^c√(x√(aα)√(aα^2+4)+α√(a)/2)-πα√(x).

with the same notation as in proof of theorem <ref>. As the bound of argument of Bessel function is the same as exponents in the proof of theorem <ref> we get the same bound.












Proof of corollaries <ref> and <ref>.  
For corollary <ref> pick a=1, and c=√(2π^2/3) in the Lemma <ref>. For corollary <ref> pick c=2π/√(15)  and a=1 in Lemma <ref>. 



















§ PROOF RELATED TO THE PROUHET-TARRY-ESCOTT PROBLEM


It is worth establishing a “baseline result" related to problem <ref> for N large, relative to
k, n, that we get easily from a Pigeonhole Argument: consider all vectors
(x, x^2,⋯, x^k) with 1 ≤ x ≤ N. The sum of n of these lie in a box of volume
n^kN^k(k+1)/2; and if two such sums belong to the same box with dimensions
N^c × N^2c×⋯× N^kc, then they give a solution to (<ref>) for all 1≤ i≤ k. The
number of non over-lapping N^c×⋯× N^kc boxes that fit inside our volume n^kN^k(k+1)/2 is at
most n^kN^(1-c)k(k+1)/2; and with a little work one can see that the large box
can be covered with approximately (up to a constant factor) this many smaller
boxes. If this (the number of smaller boxes in a covering) is smaller than the
number of sets of n vectors (x, x^2, ⋯, x^k) that produce our vector sum  (this
count is at least N^n/n! for N large enough relative to n) then we get a “collision",
that is a pair of sequences a_1, ⋯, a_n and b_1, ⋯, b_n leading to a solution to <ref>
for all 1≤ i ≤ k. In other words, we get such a solution when

    n^kN^(1-c)k(k+1)/2<N^n/n!.

For N large, then, we get that there is a solution so long as

    c> 1-2n/k(k+1).

When k is a little smaller than
√(2n), note that the RHS is negative,
implying that we can take c = 0 (since it must be non-negative).

Curiously, when k is only a little bigger than √(n) (say, √(n)log(n)), then this pigeonhole argument only gives us pairs of sequences with c near to 1.
Basically, then, we don't get a much better result for the weakening than we do for the original Prouhet-Tarry-Escott Problem, if we insist on finding solutions with c < 1/2, say.








We prove a lemma before introducing a set of solutions for the weak Prouhet-Terry-Escott problem (problem <ref>). 






For large x, let k≪√(x)/log(xT) and T:=T(x)=o(x). Then for every  1≤ r≤ k there exists c>0 such that 

    ∑_ℓ^2<xT(-1)^ℓ(xT-ℓ^2)^r/2≪√(x)(Tx)^r/4 (Ar)^r/2











Note that the proof becomes easier if we just choose r to be even. But we propose a more general case here.










Let u=o(√(x)), to be determined later. Define

    f_r(z)=(xT-z^2)^r/2/sin(π z).

Let γ be the contour in Figure <ref>. Using the residue Theorem 

    ∫_γf_r(z)dz= 2π i∑_ℓ^2<xT(-1)^ℓ(Tx-ℓ^2)^r/2.










Let z∈γ_1,γ_3. So z=t± iu√(x) and -√(xT)<t<√(xT). Then 

    | xT-z^2|^2
    =    (xT+u^2x-t^2)^2+ 4t^2u^2x.

Note that u is a constant as x tends to infinity and T=o(x). With simple computation we can conclude that the RHS is maximaized at t=0, so 
on γ_1,γ_3 we have 

    |f_r(z)|≪| xT+u^2x|^r/4e^-π u√(x)∼ (xT)^r/4 e^-π u√(x).

By assumption r≤ k≪√(x)/log(xT), so we can pick u to be large enough so as the contribution of horizental legs become small. For γ_2,γ_4 we have z=±√(xT)+it and -u√(x)<t<u√(x). We can show that

    | xT-z^2|^2
    =t^4+4t^2xT.

So we need to maximize the RHS of the following expression for t≤ u√(x)  

    |f_r(z)|≪ (t^4+4t^2xT)^r/4e^-π t

Simple computation shows that it happens when t∼ Cr for some C>0. Hence, there exist A>0 such that

    |f_r(z)|≪ A^r (xT)^r/4(r^2 + r^4/xT)^r/4≪ (Ar)^r/2 (xT)^r/4.

This completes the proof.













We could increase the height of vertical lines of figure <ref> to x^α, α>1/2, to make it possible for k to become bigger - say k≫ x^α. This in turn results in larger k=M(n) and larger error term.   









Proof of Theorem <ref>.  Let M be a large number. 

    x_i=M^2m+b-(2i-2)^2      
    y_i=M^2m+b-(2i-1)^2

Then  max(x_i^r,y_i^r)∼ M^2m+b. Lemma <ref> concludes that for x=M^2m and T=M^b and 1≤ r≤ k

    ∑_ix_i^r-∑_i y_i^r ≪ (r)^r/2+ϵM^(2m+b)r/4+m.

If we pick k≤uπ M^m/12m^2log(M) and b=1, then the result follows.








Proof of Theorem <ref>.  
We first show that f_r(M) is a polynomial in M – that is, 

    f_r(M) = c_0(r) + c_1(r)M + ⋯ + c_d(r) M^d,
 
where d is yet to be determined.  This follows upon applying the binomial theorem to the terms in the definition of f_r(M), together with the fact that ∑_|ℓ| < 2M (-1)^ℓℓ^k is a polynomial in M. The coefficients are obviously integers and we also can show the coefficients as sums involving Bernouli numbers. Note that the degree d of that polynomial doesn't depend on M.  

Let's assume that r is even. We now leverage this fact to prove that d = r-1.  To do this, note that it suffices to prove that |f_r(M)| = o_r( M^r), and |f_r(M)| ≫_r M^r-1. 

To put that another way:  fix r, and then we show that 

    lim_M →∞log( |f_r(M)|)/log(M) = r-1.

 Write f_r(M) as the contour integral 

    1/2π i∫_γ f(z) dz:=1/2π i∫_γ(4M^2 - z^2)^r/sin(π z) dz,
 
where γ is in figure <ref>. Note that because f has a removable singularity at z=± 2M, it is possible to compute the contribution of the integral in these vertical legs.












Now, one easily sees that the contribution of γ_1,γ_3 is negligible, and at least for M large relative to r the main contribution will come from the part of the contour near the real axis.  These two parts of the contour can be parametrized as z = 2M + i t and z = -2M + it, |t| ≤ 2M. So, for M large relative to r we will have that the integral is 

    ∼1/π∫_-2M^2M(-4M it + t^2)^r/sin(π it) dt    = 1/π∫_-2M^2M(-4M it)^r/sin(π it) dt + 1/π∫_-2M^2Mr(-4Mit)^r-1 t^2 /sin(π it) dt + O(M^r-2) 
       ∼ 0 + r/π (-4Mi)^r-1∫_-∞^∞t^r+1/sin(π it) dt ∼ c M^r-1,

for a constant c that depends only on r. Note that the first term of RHS is zero by symmetry. This means that f_r(M) is of degree r-1. 
Also we bound the size of f_r(M) from above in the range r ≪M/log(M).

    ∫_γ f(z) dz ∼ c M^r-1≪ e^r(log(r)+loglog(r))M^r-1.






99
berndt Berndt, Bruce C. Number Theory in the spirit of Ramanujan. Vol. 34. American Mathematical Soc., 2006.
andrew Andrews, George E. The theory of partitions. No. 2. Cambridge university press, 1998.
desalvo DeSalvo, Stephen, and Igor Pak. “Log-concavity of the partition function." The Ramanujan Journal 38.1 (2015): 61-73.
montgomerybook Montgomery, Hugh L. Ten Lectures on the interface between analytic number theory and harmonic analysis. No. 84. American Mathematical Soc. 1994.
wright34 Wright, E. Maitland. “Asymptotic partition formulae. III. Partitions into k^th powers." Acta Mathematica 63 (1934): 143-191.
gert Almkvist, Gert. “Exact asymptotic formulas for the coefficients of nonmodular functions." Journal of Number Theory 38.2 (1991): 145-160.
tao https://terrytao.wordpress.com/2015/02/07/254a-notes-5-bounding-exponential-sums-and-the-zeta-function/.
iseki Iseki, S. “A partition function with some congruence condition". American Journal of Mathematics, 81(4), 939-961. 
lehner Lehner, J. (1941). A partition function connected with the modulus five. Duke Mathematical Journal, 8(4), 631-655.
hao Hua, L. K. (1942). On the number of partitions of a number into unequal parts. Transactions of the American Mathematical Society, 51(1), 194-201.
chen <http://eslpower.org/unsolve.htm>
butler Butler, R. Wood, A. “Saddlepoint approximation for moment generating functions of truncated random variables."  The Annals of Statistics 32.6 (2004): 2712-2730.
xu Xu, J. Jing-hui Z. “Moment generating functions of random variables and asymptotic behavior for generalized Feller operators." Journal of Computational Mathematics (2000): 173-182.
Raghanderavan Raghanderavan, S. Veena, N. “The Prouhet Tarry Escott Problem: A Review." Mathematics 7.3 (2019): 227.
wooley16 T. D. Wooley. The cubic case of the main conjecture in Vinogradov’s mean
value theorem. Adv. Math., 294:532–561, 2016.
Bourgain16 J. Bourgain, C. Demeter, and L. Guth. Proof of the main conjecture in
Vinogradov’s mean value theorem for degrees higher than three. Ann. of
Math. (2), 184(2):633–682, 2016.
Pierce Pierce, Lillian B. “The Vinogradov mean value theorem [after Wooley, and Bourgain, Demeter and Guth]." arXiv preprint arXiv:1707.00119 (2017).
Montgomery Montgomery, Hugh Lowell, and Robert Charles Vaughan. "The large sieve." Mathematika 20.2 (1973): 119-134.

