A Fourier series' upper bound involving gamma function

172 Views Asked by At

I am reading Donald E. Knuth's "The Art of Computer Programming" Vol. 3 and stuck on the equation 47 and inequality 48 on Page 133,which are the follows: $$ \delta(n)=\frac{2}{\ln2}\sum_{k \ge 1} \mathfrak R\left(\Gamma(-1-2\pi ik/\ln 2)\cdot \exp(2\pi ik \lg n) \right) \tag{47} $$ $$ |\delta(n)|<0.000000173 \tag{48} $$ The author said that he only used $|\Gamma(-1+it)|=|\pi/(t(1+t^2)\sinh \pi t)|^{1/2}$ to obtain 48 from 47.
I can see that the equation 47 is actually a Fourier series, but I can't recall any properties that can help. Expanding the inequality 48: $$ \begin{align} |\delta(n)| & = \left|\frac{2}{\ln 2} \sum_{k \ge 1} \mathfrak R( \Gamma(-1-2\pi ik/\ln2)\cdot exp(2\pi ik \lg n))\right| \\ & \leq \frac{2}{\ln 2} \sum_{k \ge 1} \left| \mathfrak R( \Gamma(-1-2\pi ik/\ln2)\cdot exp(2\pi ik \lg n))\right| \\ & \leq \frac{2}{\ln 2} \sum_{k \ge 1} \left| \Gamma(-1-2\pi ik/\ln2)\cdot exp(2\pi ik \lg n)\right| \\ & = \frac{2}{\ln 2} \sum_{k \ge 1} \left| \Gamma(-1-2\pi ik/\ln2) \right| \\ & = \frac{2}{\ln 2} \sum_{k \ge 1} \left( \frac{\pi}{(2\pi k/\ln 2)(1+4 \pi^2 k^2 /\ln^2 2) \sinh(\pi \cdot 2\pi k/\ln 2)} \right)^{1/2} \\ \end{align} $$
I have no idea how to handle the $\sinh$ correctly in the above inequality. Any suggestion or hint about the equations is appreciated!

1

There are 1 best solutions below

1
On BEST ANSWER

Continuing with my question, I splitted the hyperbolic function $\sinh(z)=\frac{e^z-e^{-z}}{2}$, and noticed that $$ \text{when} \quad k\geq 1, \quad \sinh(2\pi^2 k/ \ln 2) > \exp(2\pi^2 k/ \ln 2)/4 \tag{*} $$ Expand the inequality again: $$ \begin{align} |\delta(n)| & \leq \frac{2}{\ln 2} \sum_{k \ge 1} \left( \frac{\pi}{(2\pi k/\ln 2)(1+4 \pi^2 k^2 /\ln^2 2) \sinh(\pi \cdot 2\pi k/\ln 2)} \right)^{1/2} \\ & \leq \frac{2}{\ln 2} \sum_{k \ge 1} \left( \frac{\pi}{(2\pi k/\ln 2)(4 \pi^2 k^2 /\ln^2 2) \sinh(\pi \cdot 2\pi k/\ln 2)} \right)^{1/2} \\ & \leq \frac{2}{\ln 2} \sum_{k \ge 1} \left( \frac{\pi}{(8\pi^3 k^3/\ln^3 2) \exp(2\pi^2 k/ \ln 2)/4 } \right)^{1/2} \\ & = \frac{\sqrt{2\ln 2}}{\pi} \sum_{k\geq 1} k^{-3/2} \exp(-\pi^2 k/\ln 2) \\ & \leq \frac{\sqrt{2\ln 2}}{\pi} \sum_{k\geq 1} \exp(-\pi^2 k/\ln 2) \\ & = \frac{\sqrt{2\ln 2}}{\pi}\cdot \frac{e^{-\pi^2/\ln 2}}{1-e^{-\pi^2/\ln 2}} \\ & = 0.0000002454331 \end{align} $$ I suggest that replace $4$ with a smaller number greater than $2$ in $(*)$ may approach the value $0.000000173$.