User johan andersson - MathOverflow

Answer by Johan Andersson for polynomial zero within a square

2013-05-12T16:55:20Z

Edit: I had the feeling my original answer below was much too complicated. Here is a better answer.

New answer: Given $n$ complex numbers $z_k$ and $a_k$, $k=1,\ldots,n$ we can use standard interpolation arguments to find a polynomial $q(z)$ of degree $n$ such that $q(z_k)=a_k$. For example by choosing $a_k=k$ we will get $|q(z_k)|<|q(z_j)|$ iff $ k < j$. For any bounded set $D$, we can now add a large positive constant $K$ such that $p(z)=q(z)+K$ is zero free on $D$. In your example we can choose $z_1=0$ and $z_2,\ldots,z_9$ the points on the boundary of the unit square, and we can choose the constant $K$ sufficiently large so that $p(z)$ is zero free on the unit square and we get that $|p(0)|<|p(z_k)|$ for these points

Old answer: Sure, there is. In fact given any finitely number of points on the boundary, say $z_1,\ldots,z_n$, there exists a polynomial such that $|p(0)|<|p(z_k)|$ that is zero free on the unit disc. An observation is that it follows by looking at the meromorphic function $$ f_{\epsilon}(z)=\prod_{k=1}^n z_k(z-z_k(1+\epsilon))^{-1} $$ By the construction $\lim_{\epsilon \to 0^+} f_\epsilon(0)=1$ and $\lim_{\epsilon \to 0^+} |f_\epsilon(z_k)|=\infty$. Thus we can choose an $\epsilon>0$ such that $|f_\epsilon(0)|<3/2<2<|f_\epsilon(z_k)|$. Since $f_\epsilon(z)$ is continuous and zero free on the closed unit square and analytic in the open unit square, a variant of Mergelyan's theorem of mine, http://arxiv.org/abs/1010.0850 shows that we can approximate the function arbitrarily closely (in sup norm) on the unit square by a polynomial without zeros (this is where my variant is needed) in the unit square. If we find such a polynomial $p(z)$ that approximates the function $f_\epsilon(z)$ with an error less that $1/4$ then the inequality $|p(0)|<|p(z_k)|$ holds.

Answer by Johan Andersson for Pair correlation for the Riemann zeros and $(\zeta^\prime(s)/\zeta(s))^\prime$

2013-02-10T19:42:14Z

I believe the comments of joro and Carlo Benakker right under your question is to the point. Since the zeroes close to $s$ will be the ones that contributes in the sum, the zeroes close to s must be computed first and in order to do that several values of the zeta-function must certainly be calculated and the time for each such computation (and zero) will certainly not be less than computing any other particular value of $\zeta(s)$ or $\zeta'(s)$.

As for calculating a particular value $\zeta(s)$ the recent method of Ghaith Hiary http://arxiv.org/abs/0711.5005 "Fast methods to compute the Riemann zeta function" (published in Annals of Mathematics 2011) contains the fastest method known. He shows a method that calculates the value of $\zeta(1/2+it)$ with an error term less than $|t|^{-N}$ in time $O_{\varepsilon,N}(t^{4/13+\varepsilon})$. The method of Odlyzko and Schönhage "Fast algorithms for multiple evaluations of the Riemann zeta function", doi:10.2307/2000939 is faster if sufficiently many values of $t$ needs to be calculated, i.e. it can calculate $\sqrt T$ values in the range $[T,T+\sqrt T]$ in time $O_\varepsilon(T^{1/2+\varepsilon})$.

Now, In Hiary's paper it might look like he only considers the critical line. However in fact his method works for any value in the critical strip. Indeed in part of his argument he considers just the line Re$(s)=0$, but then he writes "It is clear that the restriction $\sigma=0$ is not important and a similar conclusions can be drawn for other values of $\sigma$" (page 6, second to last paragraph in Hiary's paper). It is true that his main interest is the critical line, but the algorithm holds for any $s$ in any vertical strip such as the critical strip.

Now to calculate $\zeta'(s)$ up to error of order $t^{-N}$ it is sufficient to calculate $\zeta(s+ih)$ and $\zeta(s-ih)$ with error less than $t^{-3N/2-1/4}$ for $h=t^{-N/2-1/4}$ and consider the difference quotient $(\zeta(s+ih)-\zeta(s-ih))/h$ by also using that $\zeta'''(s) =O(\sqrt t)$ in the critical strip and some version of the mean value theorem inequality. It is simple to use finite difference quotients to calculate $\zeta^{(k)}(s)$ up to any desired degree of accuracy. Thus we can certainly use this method to calculate for example $$ \frac d {ds} \frac{\zeta'(s)}{\zeta(s)}= \frac{\zeta''(s)\zeta(s)-\zeta'(s)^2}{\zeta(s)^2} $$ by this method. This method should not be computionally wasteful.

Answer by Johan Andersson for Saying things rapidly about integer factorisations

2013-02-01T13:14:26Z

While the method used is not related to the work you mention in the question, there is recent work of Andrew Booker, Ghaith Hiary and Jon Keating where they develop an algorithm for determining a non trival lower bound (assuming GRH) for the square free part of the number $N$, i.e. if
$$ N=\Delta m^2, $$ where $\Delta$ is square free they obtain a lower bound for $\log \Delta$, by using the Weil explicit formula for certain $L$-functions associated to $N$. I do not find the relevant paper (in progress?), but there is a slide on Hiary's homepage http://www.maths.bristol.ac.uk/~maxgh/ from a talk he has given on the topic (that I attended). In particular they manage to show that assuming the Riemann hypothesis for the relevant Dirichlet L-functions, RSA-210 is not square-full (there exists at least one prime factor in the factorization of RSA-210 that occurs just once), a number that has yet to be factored, so for example it can not be of the form $p^2q^3$. Of course it is likely to be a product of just two prime factors, but we do not yet have a proof of that.

Answer by Johan Andersson for On the location of zeros of L functions from modular forms

2013-01-14T15:01:49Z

When it is not a Hecke-Eigen form, the Hecke L-series connected with the modular form does not have an Euler product. However it can still be written as a linear combination of Hecke L-series that have Euler-products. Thus the situation will resemble the case of linear combinations of Dirichlet L-series. In particular we can use joint Voronin universality to obtain $\gg T$ zeroes in any strip $1/2<\sigma_1<\Re(s)<\sigma_2 < 1$, $-T < \Im(s)< T.$ These results follows from the analytic properties of the Rankin-Selberg zeta-function (which gives "independence results" for Hecke eigenvalues of primes attached to different cusp forms). You should be able to find results of this kind in Steuding's SLN "Value Distribution of L-functions".

Also the results of Davenport-Heilbronn for the Hurwitz zeta-function can be proved, i.e. For any $\epsilon>0$ there exists $\gg T$ zeroes with $1<\Re(s)<1+\epsilon$ and $-T < \Im(s) < T $.

Stronger results corresponding to results of Karatsuba, Bombieri, Hejhal and Selberg for Dirichlet L-function that holds close to the critical line likely also holds. I think the russian school (Irina Rezvyakova) has proved results in this direction.

Answer by Johan Andersson for What are the fallacies that this RH inequality may fail at most finitely often?

2012-07-26T10:45:48Z

I suspect the mistake is in relying on Sage or Maple in the last step. Instead use the asymptotic expansion of li(x) ( http://en.wikipedia.org/wiki/Logarithmic_integral_function ) $$\operatorname{li}(x)=\frac x {\log x}+\frac{x}{\log^2 x}+O \left(\frac x {\log^3 x} \right)$$ to obtain an asymptotic expression of $G(n)$. Letting $$x=\frac 1 4 \left(\frac {\log \log n-0.975}{\log n}+2 \right)^2 n \log n$$ we see that $$x = n \log n \left(1+\frac{\log \log n}{\log n}- \frac{0.975}{\log n} +O \left( \frac{\log \log n}{\log^2 n} \right) \right) $$ and that $$\log x=\log n+\log \log n+\frac{\log \log n}{\log n}-\frac{0.975}{\log n}+O \left(\frac {\log \log n}{\log^2 n} \right).$$ With some more calculation we get $$\frac x {\log x}=n-\frac{0.975 n}{\log n}+O \left(\frac {n \log \log n}{\log^2 n} \right) $$ By the first two terms in the asymtotic expansion of li(x) we get that $$ \operatorname{li} (x)=n+\frac{0.025n}{\log n}+O \left(\frac {n \log \log n}{\log^2 n} \right) $$ and thus $$G(n)=\frac{0.025 n}{\log n}+O \left(\frac {n \log \log n}{\log^2 n} \right) $$ and $G(n) \to \infty$ as $n\to \infty$.

Answer by Johan Andersson for non-trivial zeros of partial zeta functions

2012-05-19T11:35:05Z

Micah's answer answers your Q1. My reply gives some information on your Q2. Let us assume that $1 \leq a\leq N$ for simplicity (this condition can be removed). Your zeta-functions $\zeta$ and $\Psi$ can be expressed by the Hurwitz zeta-function http://en.wikipedia.org/wiki/Hurwitz_zeta_function. For your first function $$\zeta(s;N,a)=N^{-s} \zeta \left(s,\frac a N \right).$$ Davenport and Heilbronn proved that for any $c>0$, $a/N \neq 1/2,1$ there exists $\gg T$ zeros of this function in the strip $1<\Re(s)<1+c, | \Im (s)| < T $. By Voronin universality for the Hurwitz zeta-function the same can be said in any strip $1/2<\sigma_0< \Re (s)<\sigma_1<1$ (this can be found for example in Jörn Steuding's SLN or Garunkstis-Laurincikas book on the Lerch zeta-function).

Your second function can also be expressed in terms of the Hurwitz zeta-function $$\Psi(s,\omega;N,a)=N^{-s} \left(\zeta\left(s,\frac a N\right)+\omega(-1)\zeta \left( s,1-\frac a N \right) \right).$$ In this case joint universality of the Hurwitz zeta-function (see same references as above) can be used to show that except when $\Psi$ has an Euler-product (which only occurs for some small special cases when $ a / N$ equals 1/6, 1/4, 1/3, 1/2, 2/3, 3/4, 5/6, or 1.) there are $\gg T $ zeros in any strip $1/2<\sigma_0< \Re (s) < \sigma_1 < 1$ and $|\Im(s)| < T$. Davenport-Heilbronn's result for $\Re(s)>1$ can be obtained in this case as well.

For the special cases where your function has an Euler-product it will essentially be a Dirichlet L-function or the Riemann zeta-function, and its zeros will be the same.

Answer by Johan Andersson for Mertens' function in time $O(\sqrt x)$

2012-05-10T18:45:06Z

This is really a response to Dror Speiser's comment (but it is too long to give as a comment), and gives an analytic $O(n^{1/3+\epsilon})$ time and $O(n^{1/6+\epsilon})$ space algorithm to count the number of square free numbers less than $x$ (thus improving on the complexity of the algorithm given in the Jakub Pawlewicz paper cited in the question). If we do exactly in the same way as in my other answer for $$\sum_{n\leq x} |\mu(n)|$$ instead of $$\sum_{n\leq x} \mu(n)$$ by using the fact that $$\frac{\zeta(s)}{\zeta(2s)} = \sum_{n=1}^\infty |\mu(n)| n^{-s}$$ it is true that the time complexity will be $O(x^{1/2+\epsilon})$. There is however a way to combine the analytic method (which is essentially the same as in Lagarias-Odlyzkos 1987 paper "Computing $\pi(x)$ an analytic method" http://www.dtc.umn.edu/~odlyzko/doc/arch/analytic.pi.of.x.pdf) with the elementary identity $$ S(n)=\sum_{d=1}^{\lfloor \sqrt n\rfloor} \mu(d) \lfloor \frac n {d^2} \rfloor $$ that is Pawleviec's starting point in obtaining his algorithm. Let $\Phi$ be defined as in my other answer, i.e. let $\Phi(x)$ be a smooth test function such that $\Phi(x)=1$ for $x<0$ and $\Phi(x)=0$ for $x>1$. Consider the identity $$ \sum_{n\leq x} |\mu(n)| =\sum_{n=1}^\infty |\mu(n)| \Phi \left( \frac {n-x} {x^{2/3}} \right ) - \sum_{x< n < x + x^{2/3} } |\mu(n)| \Phi \left(\frac {n-x} {x^{2/3}} \right)$$

The first sum can be estimated by a complex integral of length $x^{1/3+\epsilon}$ and by the Odlyzko-Schönhage algorithm it can be calculated in $O(x^{1/3+\epsilon})$ time (and $O(x^{1/6+\epsilon})$ space). The remaining sum will have length $O(x^{2/3})$ so might at first glance not be so simple to treat. I claim however that in fact it can be calculated in $O(x^{1/3+\epsilon})$ time. This is where using the elementary identity is handy. Let $\Psi(x)=0$ for $x<0$ and $\Psi(x)=\Phi(x)$ for $x \geq 0$ (this will have a discontinuity at $x=0$) By a similar elementary identity we obtain

$$\sum_{x< n < x + x^{2/3} } |\mu(n)| \Phi \left(\frac {n-x} {x^{2/3}} \right) = \sum_{d=1}^{\lfloor \sqrt {x+x^{2/3}}\rfloor} \mu(d) \sum_{k=1}^\infty \Psi \left(\frac {d^2k-x} {x^{2/3}} \right). $$ For any $d$ the inner sum can be calculated fast (certainly in $O(x^\epsilon)$ time), by either noticing that the sum is empty, just contains one element or the Poisson summation formula. The trick now is to see that there will only be $O(x^{1/3})$ integers $d$ where the inner sum (in $k$) is non empty, namely $d$ must either be $O(x^{1/3})$ or belong to an interval $(\sqrt{ x/k},\sqrt{(x+x^{2/3})/k})$ for $k \leq x^{1/3}$ and there are only $O(x^{1/3})$ such $d$. Now if we can calculate the values of $\mu(d)$ fast (simple sieving seems more difficult in this case) we obtain the desired algorithm. Determining $\mu(d)$ basically comes down to factoring the number. However it is sufficient to determine the factors less than $d^{1/3}$ since if we know that all prime factors are greater than $d^{1/3}$, then either it has one or two prime factors. We can determine if it is a prime fast by the Agrawal-Kayal-Saxena algorithm, then of course $\mu(d)=-1$. If it has two prime factors either $\mu(d)=0$, but then it has to be a square, and it can be easily checked, or $\mu(d)=1$. Now factoring the $O(x^{1/3})$ numbers of size $O(x^{1/2})$ into all prime factors less than $x^{1/6}$ will take $O(x^{1/3+\epsilon})$ time and $O(x^{1/6+\epsilon})$ space by Bernstein's algorithm http://cr.yp.to/papers/sf.pdf. I might possibly write up this answer as a paper proper. If anyone has seen these arguments anywhere else or have references I would be interested.

Answer by Johan Andersson for Computing the Mertens function

2012-05-02T16:15:39Z

As I indicate in the answer http://mathoverflow.net/questions/95726/mertens-function-in-time-o-sqrt-x, there is a method in Lagarias-Odlyzkos 1987 paper "Computing $\pi(x)$ an analytic method" (which I sketch in that answer) that calculates $M(x)$ on $O(x^{1/2+\epsilon})$ time. The Kotnik-Van de Lune paper that Gjergji Zaimi cites indeed also cites this paper. While the methods that depend on values of the Riemann zeta-function (like the Lagarias-Odlyzko method) might be asymtotically faster, the combinatorial identities are simpler to implement, and might also be faster depending on the ranges of $x$ considered.

Answer by Johan Andersson for Mertens' function in time $O(\sqrt x)$

2012-05-02T13:49:09Z

Well,

Although this does not answer your particular question of whether the paper is right, it seems rather straightforward to obtain the $O(x^{1/2+\epsilon})$ result for calculating the sum $\sum_{n \leq x} \mu(n)$ by using the same idea as in my answer to http://mathoverflow.net/questions/81443/fastest-algorithm-to-compute-the-sum-of-primes/81545#81545. Let as in that answer $\Phi(x)$ be a smooth test function such that $\Phi(x)=1$ for $x<0$ and $\Phi(x)=0$ for $x>1$. The difference here is that we consider a sum $$ \sum_{n\leq x} \mu(n) =\sum_{n=1}^\infty \mu(n)\Phi \left( \frac {n-x} {\sqrt x} \right ) - \sum_{x< n < x + \sqrt x } \mu(n) \Phi \left(\frac {n-x} {\sqrt x} \right)$$ over the Möbius function instead of a sum over primes. The first sum can be calculated by the integral $$ \sum_{n=1}^\infty \mu(n)\Phi \left( \frac {n-x} {\sqrt x} \right )= \frac 1 {2 \pi i} \int_{c-\infty i}^{c+\infty i} \frac 1 {\zeta(s)} \int_0^\infty \Phi \left(\frac{y-x}{\sqrt x} \right)f(y) y^{s-1} dyds, (c>1)$$ which can be calculated by the Odlyzko-Schönhage algorithm in time $O(x^{1/2+\epsilon})$ in the same way as in that answer. The remaining sum will be over an interval of length $\sqrt x$. Sieving techniques can determine the Möbius function for all these numbers fast and the time it will take to calculate that sum is of the order of $O(\sqrt x \log x)$.

Update: I looked at Lagarias-Odlyzkos 1987 paper "Computing $\pi(x)$ an analytic method". On page 8 at the bottom of the page I quote "The basic ideas underlying analytic $\pi(x)$ algorithms can be used for computing other arithmetical functions, such as $$ M(x) =\sum_{n\leq x} \mu(n).$$ Thus they were certainly aware of the $O(x^{1/2+\epsilon})$ time complexity for calculating $M(x)$. What I describe above is indeed a variant of the Lagarias-Odlyzko method.

Answer by Johan Andersson for A note by N. A. Carella on zero-free regions

2012-04-12T13:45:13Z

Well,

In this case it is a short elementary paper (6 pages) and it is easy to verify, although just the length of the paper and the importance of the result and some other aspects of the paper, such as the fact that it is in general mathematics part of arxiv and it does not seem as the autor uses latex is sufficient to be quite sceptical about the claim. It is easy to find mistakes. The paper has 6 pages. The first part seems to contain some standard results in the area. The proof of the new claimed very strong result, Theorem 1 is just one page long, and it starts on page 4, so it is sufficient to read that part. The author tries to use the fact that $$ \theta(x+y)-\theta(x)>0, $$ where $$ \theta(x)=\sum_{ p < x } \log(p),$$ whenever $y \gg x^{21/40} $, which is a nice result of Baker-Harman-Pintz to prove the claimed zero free region. This is theorem 1 in the paper. It is easy to see that the claimed proof gives no such result. The author gives the elementary inequality $$ \theta(x+y)-\theta(x) < y (\log x)^3.$$ This is certainly true in relevant ranges of $x$ and $y$. However the author then somehow uses this inequality in the wrong direction into something that essentially boils down to (Eq 4 in the paper does not hold in general) $$ 0< \theta(x+y)-\theta(x) < y (\log x)^3 < \theta(x+y)-\theta(x). $$ Since this is obviously false the author obtains several contradictions, one of which is supposed to prove Theorem 1 (at least that is my guess how the author comes to that conclusion. The "proof" is not clear at all).

Answer by Johan Andersson for Convergence of the summation 1/p^(1+iy) (over all primes p with y a nonzero real number)

2012-01-27T15:43:23Z

This is always convergent for any real $y \neq 0$. This follows from the fact that the related integral $$\int_2^\infty \frac{x^{iy-1}}{\log x} dx $$ is convergent (to see this use the substitution $t=\log x$ ), and say the prime number theorem with some weak error term, in fact $$ \pi(x)=\frac x {\log x} \left( 1+O \left( \frac 1 {\log x} \right) \right) $$ is sufficient. In a similar spirit the similar sum $$ \sum_{n=1}^\infty n^{-1+iy} $$ is not convergent for any $y$ (while bounded for $y \neq 0$ the partial sums will oscillate). This can be seen from the related integral $$ \int_2^\infty x^{iy-1} dx $$ and the same substitution.

Answer by Johan Andersson for averages of Euler-phi function and similar

2011-12-30T12:26:37Z

A more analytic way to see this is through Dirichlet series, namely we know that (H&W as mentioned in the other answers is a good reference, but the identity can be seen by the Euler product) $$ \sum_{k=1}^\infty \phi(k) k^{-s}= \frac{\zeta(s-1)}{\zeta(s)}. $$ Perron's formula gives $$ \sum_{k=1}^n \phi(k) =\frac 1 {2 \pi i}\int_{c-\infty i}^{c+\infty i} \frac{\zeta(s-1)}{\zeta(s)} \frac{x^s} s ds, \qquad (n < x < n+1)$$ where $ c > 2$ is large enough for the Dirichlet series to be absolutely convergent. From moving $c>2$ to $ 1 < c < 2$ we pick up a residue at $s=2$ coming from the zeta-function's pole at Re$(s)=1$, from where the main term comes. This will be exactly $\frac {x^2} {2 \zeta(2)}=3 x^2/\pi^2$.

The remaining integral can be estimated as an error term (the strong form of the error term as mentioned above will be more difficult to obtain this way however).

The Dirichlet series argument why all the noise disappears (The error term is rather good) is simply that the Dirichlet series in the region $ 1 < $ Re $ (s)<2 $ does not behave too badly (i.e. has no poles, and does not grow too fast when Im$(s)\to \infty$). This method also works for other arithmetical functions (often with worse error terms), for example divisor problems. Cases more difficult to treat with the convolution method, where even more noise remains because the function has poles includes for example estimating sums of the Möbius function or the Von Mangoldt function (the RH gives much better estimates than known unconditional estimates in these cases).

Answer by Johan Andersson for Fastest Algorithm to Compute the Sum of Primes?

2011-11-21T19:53:44Z

Edit Nov 22: Changed the condition of the test function $\Phi$ somewhat to simplify my argument (removed one sum in the identity below).

Although I like Charles' answer and its application of the Chinese remainder theorem, let me give you a different take on the problem. It is possible to use an analytic method more directly (similar to the Lagarias-Odlyzko method), just using the Riemann zeta-function and not any theory of the Dirichlet L-functions (or primes in arithmetical sequences). This method can treat rather arbitrary sums $$ \sum_{ p < x } f(p) $$ for smooth functions $f$.

The idea is to consider the identity $$\sum_{ p < x } f(p) =\sum_{p} f(p)\Phi \left( \frac {p-x} {\sqrt x} \right ) - \sum_{x< p < x + \sqrt x } f(p) \Phi \left(\frac {p-x} {\sqrt x} \right), $$ where $\Phi(x)$ is smooth test function such that $\Phi(x)=1$ for $x<0$ and $\Phi(x)=0$ for $x>1$. It is clear that the last sum can be calculated in $O( x^{1/2} )$ time (say sieving out the primes in the interval, and explicit calculation). The idea is now to use the Mellin-transform identity $$ \sum_{p}f(p)\Phi \left( \frac {p-x} {\sqrt x} \right )= \frac 1 {2 \pi i} \int_{c-\infty i}^{c+\infty i} \sum_{p} p^{-s} \int_0^\infty \Phi \left(\frac{y-x}{\sqrt x} \right)f(y) y^{s-1} dyds. (c>1)$$ The point here is that the Mellin transform $\int_0^\infty \Phi(\frac{y-x}{\sqrt x})f(y) y^{s-1}dy$ is small when $|\Im(s)|>x^{1/2+\epsilon}$ and $\Re(s)=c$ for any $\epsilon>0$, so that part of the integral can be discarded. The Dirichlet series $\sum_{p} p^{-s}$ can be expressed in terms of the logarithm of the zeta function for the arguments $ks$ (summing over $k$). Now the Odlyzko-Schönhage algorithm (Quite nice algorithm, uses fast fourier transform) allows us to calculate the values of the Riemann zeta-function for say $s=c+it$ for $ |t| < x^{1/2+\epsilon}$ in $O(x^{1/2+\epsilon+o(1)})$ time. We also remark that the Weil explicit formula can be used instead of this complex integral (then the zeros of the Riemann zeta-function needs to be calculated fast, but this can also be done by the Odlyzko-Schönhage algorithm). This means that the total time to calculate $\sum_{ p < x } f(p)$ will be $O(x^{1/2+\epsilon})$ for any $\epsilon>0$.

Note that the same argument applies when primes in arithmetical progression are concerned (see my comment on Charles answer). Since the Odlyzko-Schönhage algorithm also holds for the Dirichlet L-functions, this case can be treated in the same way.

Answer by Johan Andersson for Near points in several arithmetic progressions

2011-11-15T18:35:33Z

This follows from the Kronecker's approximation theorem (With the conditions modified. See edit below).

Assume without loss of generality that $a_k$ are positive, that $c_1 \leq c_k$ and $0 \leq c_k < a_k$. Let $n_1=n$ and $n_k=\lfloor na_1/a_k\rfloor$ for $k=1,\ldots,K$. Then $n_1 a_1+c_1-(n_k a_k+c_k)=n a_1 -\lfloor na_1/a_k\rfloor a_k+c_1-c_k=c_1-c_k + $ { $ n a_1/a_k $ }$a_k$

By Kronecker's approximation theorem there exists some $n$ such that $|c_1-c_k + $ {$n a_1/a_k $}$a_k|<\epsilon/2$ for each $k=1,\ldots,K$. The conclusion follows from the triangle inequality.

Edit: As Noam D. Elkies remarked in his answer what we use here is in fact the linear independence over $\mathbb Q$ of the reciprocals of the numbers, $1/a_k$ (Or equivalently in my application of the Kronecker's approximation theorem, the numbers $a_1/a_k$ ), not the numbers $a_k$ themselves. This means that the question as posed is not true, but it is true when the conditions are modified.

Answer by Johan Andersson for lower bound for $\Re\zeta(1+it)$

2011-11-15T12:29:01Z

There is no lower bound for Re$(\zeta(1+it))$. This can be found in Lamzouri's paper http://www.math.uiuc.edu/~lamzouri/distribzeta.pdf (see e.g. page 3, formula (5)). (Choose $\tau$ large enough, $\theta_1=3\pi/4$ and $\theta_2=5\pi/4$ for and substract). The results of Lamzouri however also implies that on average the argument of $\zeta(1+it)$ is small and that Re$(\zeta(1+it))$ is positive more often than it is negative.

Answer by Johan Andersson for Analytic continuation of ordinary Dirichlet series

2011-11-03T18:11:21Z

Well, a simple counter example is $$A(s)=\sum_{n=1}^\infty a_n n^{-s}= e^{\eta(s)},$$ where $$\eta(s)=\sum_{n=1}^\infty (-1)^{n-1} n^{-s}=(1-2^{1-s})\zeta(s).$$ This Dirichlet series is obviously meromorphic since it is in fact entire and it is also absolutely convergent on some half plane Re$(s)>c$. This entire function is not of finite order by the functional equation of the Riemann zeta-function and Stirling's formula.

Update: An even simpler example along the same lines is $$B(s)=\sum_{k=0}^\infty \frac{2^{-ks}}{k!} =e^{2^{-s}}.$$ This Dirichlet series is an entire function that is absolutely convergent in the full complex plane, so it is absolutely convergent for any half plane Re$(s)>c$. However we have that $B(-x)= e^{2^x}$, and thus it does not fulfill $B(-x)\ll e^{x^c}$ for any $c>0$ and it is not an entire function of finite order. If we would like to have a meromorphic function with some pole that has some abscissa of convergence we can consider $C(s)=\zeta(s)+B(s)$. This function is an ordinary Dirichlet series that is absolutely convergent if and only if Re$(s)>1$, has a pole at Re$(s)=1$ and meromorphic continuation to the entire complex plane, but it does not have finite order.

Answer by Johan Andersson for What are the analytic properties of Dirichlet Euler products restricted to arithmetic progressions?

2011-02-17T14:32:26Z

Well, Peter's answer is overkill for this particular problem. While this zeta-function will certainly be a Burgess zeta-function, the study of the zeta-function of this particular kind will be much simpler, and its properties can be directly deduced from properties for the Dirichlet L-functions. For simplicity I will show how to do this in the case $\chi(n)=1$ in your question, although the general character case can be treated similarly, since if we assume that $\chi$ is a character mod $N$ then $\chi \chi_1$ will be a character mod $Nq$ whenever $\chi_1$ is a character mod $q$.

Let $$ B(s)=\prod_{p \equiv a \pmod q} (1-p^{-s})^{-1}.$$ Taking the logarithm we find that $$\log B(s)= \sum_{n=1}^\infty \frac{B_0(ns)} n,$$ where $$ B_0(s)= \sum_{p \equiv a \pmod q} p^{-s}$$ is some variant of the prime zeta-function. For the half plane Re$(s)>1/2$ the terms when $n \geq 2$ will be absolutely convergent and the main term will be $B_0(s)$. For the Dirichlet $L$-series $L(s,\chi)$ we have similarly that $$ \log L(s,\chi) = \sum_{n=1}^\infty \frac{L_0(ns,\chi^n)} n,$$ where $$ L_0(s,\chi)= \sum_{p} \chi(p) p^{-s}.$$ By Möbius inversion we get $$L_0(s,\chi)= \sum_{n=1}^\infty \frac{\mu(n)}{n} \log L(ns,\chi^n).$$ It is simple to see from the definitions of the Dirichlet series and using the fact that $\sum_{\chi \pmod q}\chi(a)=\phi(q)$ if $a \equiv 1 \pmod q$ and 0 otherwise that $$ B_0(s)= \frac 1 {\phi(q)} \sum_{\chi \pmod q} \overline{\chi(a)} L_0(s,\chi).$$ By combining these results we find that $$ \log B(s)= \frac 1 {\phi(q)} \sum_{\chi \pmod q} \overline{\chi(a)} \sum_{n=1}^\infty \frac 1 n \sum_{d|n} \mu \left(\frac n d \right) \log L(ns,\chi^d). $$

The most important term will come from $n=1$ since the other terms will be absolutely convergent for Re$(s)>1/2$. Thus we have that $$ \log B(s)=\frac 1 {\phi(q)} \sum_{\chi \pmod q} \overline{\chi(a)}\log L(s,\chi)+ R(s),$$ where $R(s)$ is absolutely convergent for Re$(s)>1/2$. This means that we can write $$ B(s)= \prod_{\chi \pmod q} L(s,\chi)^{\overline{\chi(a)}/\phi(q)} A(s),$$ where $A(s)$ is a Dirichlet series absolutely convergent and nonvanishing for Re$(s)>1/2$. In particular it means that under the Generalized Riemann hypothesis $(s-1)B(s)^{\phi(q)}$ will be a holomorphic nonvanishing function for Re$(s)>1/2$. By this method it will be possible to get an analytic continuation up to Re$(s)=0$ (its natural boundary should be Re$(s)=0$ since singularities coming from the zeros of the L-functions will be dense close to that line), with exeption for singularities at $\rho/n$ where $\rho$ is a zero of some Dirichlet L-function and $1/n$.

Thus the study of the analytic properties of this zeta-function will be simple consequences of the properties of the Dirichlet L-functions.

Answer by Johan Andersson for Lower bounds on (truncated) Fourier transform of functions of constant modulus and bounded derivative

2011-02-15T18:19:26Z

It is an interesting problem which is related to some recent work of mine. The reason for why I started to work on similar problems is because connections to a problem of Ramachandra on Dirichlet polynomials, connections to the nordic school of Hardy classes of Dirichlet series (Hedenmalm, Saksman, Seip, Olsen, Olofsson, Lindqvist and others), as well as universality questions for zeta-functions and their properties on the line Re(s)=1.

While my papers are not quite finished, I have put two early preprints on my homepage, On a problem of Ramachandra and approximation of functions by Dirichlet polynomials with bounded coefficients and On generalized Hardy classes of Dirichlet series. I have talked about some of these problems at analytic number theory conferences in India. Like in your paper I have considered Dirichlet series (it should be possible to obtain something like Theorem 2.1 in your paper by my method also, although I have not stated a direct analogue in my paper).

Now your problem in the question is rather easy for small $\omega$ so we will from now on assume that $\omega>1/2$. In fact if $\omega<1/2$, then $|f(0)|>1/2$ and $\int_0^K |\hat f(t)^2|dt \geq \min(1/10,K/10)$ (constants not chosen in an optimal way)

In my papers on Dirichlet series I have used a somewhat different method than you use in your paper, namely the Jensen inequality on the logarithmic integral in a half-plane. This method is applicable for the problem at hand. Lemma 7 in my paper ``On generalized Hardy classes of Dirichlet series'' can be used with $\sigma=0$ and $L(it)=\hat f(-t)$ and we obtain $$\frac D \pi \int_{-\infty}^\infty \frac {\log^- |\hat f(t)|} {D^2+t^2} dt \leq \frac D \pi \int_{-\infty}^\infty \frac {\log^+ |\hat f (t)|} {D^2+t^2} dt - \log |\hat f(iD)|. $$ For similar results see also Koosis - The logarithmic integral. (Remark Feb 16: The above inequality is an equality if the function is non-zero on a half plane. The inequality follows from Jensen's formula on a disc by mapping the half plane on the disc by the standard holomorphic bijection where $iD$ goes to $0$) The reason why we can do this is that with the definition of the fourier-transform in your question it means that $ \hat f(z)$ will be a bounded analytic function in the half plane Im$(z) \geq 0$.

Now in this case we also have that $\log^+ |\hat f (t)|=0$ since $ |\hat f (t)| \leq 1$. Thus the inequality simplifies to $$\frac D \pi \int_{-\infty}^\infty \frac {\log^- |\hat f(t)|} {D^2+t^2} dt \leq - \log |\hat f(iD)|.$$ It is not too difficult to see that for $\omega>1/2$ $$ |\hat f(i\omega)|= \left|\int_0^1 e^{i \phi(x)-\omega x} dx \right|>\frac {1} {10 \omega}. $$ (The constant $10$ not chosen optimally). Thus we can choose $D=\omega$ and it is clear that $$ \int_0^K \log^- |\hat f(t)| dt < \frac \pi {\omega} \left({\omega^2+K^2} \right) \frac {\omega} \pi \int_{-\infty}^\infty \frac {\log^- |\hat f(t)|} {\omega^2+t^2} dt $$ From these estimates we see that $$ \frac 1 K \int_0^K \log^- |\hat f(t)| dt< \frac {\pi(\omega^2+K^2)}{\omega K} \log (10 \omega). $$ Now we can use the Jensen inequality $$ \exp\left(\frac 1 K \int_0^K \log |\hat f(t)| dt\right)< \sqrt{\frac 1 K \int_0^K |\hat f(t)|^2 dt} $$ We get the lower bound $$ K \left(\frac 1 {10 \omega} \right)^{2\pi (\omega^2+K^2)/(K \omega)} \leq \int_0^K |\hat f(t)|^2 dt $$ for $\omega>1/2$. If $c>2 \pi$ and $\omega/K$ is sufficiently large this gives a lower bound $$\omega^{-c \omega/K} \leq \int_0^K |\hat f(t)|^2 dt$$ which is weaker than your expected $e^{-c \omega/K}$. At least we have an explicit lower bound.

Updated Feb 16: In the case where both $\omega$ and $K$ are large but still $\omega>K$ this can be improved by the following trick. Let $g$ be the convolution of $\hat f$ with a non negative test-function $\Phi(t/K)$, such that $\hat \Phi(0)>0$ where $\Phi$ has support on $[0,1/2]$ . Then use Jensen's inequalities on the function $g$ instead of $\hat f$ as above. The advantage with this is that it then follows that $|\hat g(iw)| \gg K/\omega$ and thus we can get the lower bound (by using Jensen's inequality w.r.t the L^1-norm instead of the L^2-norm.) $$(\omega/K)^{-c \omega/K} \leq \frac 1 K \int_0^{K/2} |g(t)| dt$$ for some constant $c>0$. Since $$ g(t)=\int_0^t \Phi((t-x)/K) \hat f(x) dx$$ it is clear by the triangle inequality that $$\frac 1 K \int_0^{K/2} |g(t)| dt = \frac 1 K \int_0^{K/2} \left|\int_0^t \Phi((t-x)/K)\hat f(x) \right| dx \leq $$ $$\leq \frac 1 K \int_0^{K/2} |f(x)| dx \int_0^{K/2} |\Phi(x/K)| dx \leq c \int_0^{K/2} |\hat f(x)| dx $$ The inequality
$$K^{-1} (\omega/K)^{-c \omega/K} \leq \int_0^{K/2} |\hat f(t)|^2 dt$$ follows by the Cauchy-Schwarz inequality for some constant $c>0$.

This formula just use involves dimensionless quantity $\omega/K$ as expected. Since the function $E(K)$ is increasing in $K$ it gives the lower bound $E(K) > C_0 K^{-1}>0$ for $1 \leq \omega \leq K$ for some absolute constant $C_0$.

Answer by Johan Andersson for Prime factorization of n+1

2011-02-10T11:35:04Z

To elaborate on azorne's answer. We can do it in a way reminding of how we can take $n$'th powers modulo a number in about $\log n$ time.

Assume that there is a fast way to do what you want, and that we want to factor $n$. Then either $n$ or $n-1$ is divisible by 2. If $n-1$ is divisible by 2 then this reduces down to factor $(n-1)/2$ + one operation of knowing the factorization of $n-1$ to obtain a factorization of $n$. If $n$ is divisible by two we can just divide by two to reduce the factorization to the factorization of $n/2$.

Thus we see that to factor $n$ takes at most the time to factor $[n/2]$ + One operation of knowing the factor of $n-1$ to factor $n$.

If we do this in $\log_2 n$ steps we will come down to trivial numbers to factor, and thus we see that the time it takes to factor a number $n$ will be at most $\log_2 n \times $ "the maximum time it takes to go from knowing the factorization of $m$ to factor $m+1$ for $m \leq n$". This can certainly not be fast (e.g. polynomial time in $\log n$) since it would give a polynomial time algorithm (in $\log n$) to factor an arbitrary number $n$. No such algorithm is known of course. The number field sieve is expected to be the fastest known algorithm discovered yet, although the estimates for the time complexity it takes is just estimated heuristicly and is not proven rigorously.

Answer by Johan Andersson for What is the best known estimate for the place of the prime gap with length 1.609*10^18?

2011-02-08T13:04:42Z

Well, Wikipedia's page on Bertrand's postulate which Scott referred to in his answer does not cite the strongest estimates on this problem. The paper of Olivier Ramaré and Yannick Saouter MR 2004a:11095 "Short effective intervals containing primes. J. Number Theory 98 (2003), no. 1, 10–33 yield stronger result. They prove that the interval $[x(1-1/\Delta), x]$ contains a prime for $x \geq 10 726 905 041$ and $\Delta=28 313 999$. In fact they have a table that gives even stronger result in the relevant range for this problem. If we look at Table 1 from their paper we get that for $x \geq e^{60}$ we can choose $\Delta=209 267 308$. We thus need to determine $x$ so that $$ \frac x {209 267 308} <1.609 \cdot 10^{18}$$ Computation shows that $x<3.367\cdot 10^{26}$. Since $\log(3.367\cdot 10^{26})=61.1>60$ this is permissable. This gives a better estimate than Charles and Scott's answers above.

It should be remarked that already Ramaré-Saouter used these estimates for the Ternary Goldbach problem. However due to a shorter range where the Goldbach problem had been checked at that time they did get the shorter range $1.13256\cdot 10^{22}$ (Corrollary 1) than using the recent computer checked bounds for the Goldbach problem.

Answer by Johan Andersson for How many consecutive composite integers follow k!+1?

2011-02-02T14:54:12Z

This seems like an interesting problem. Prime gap problems are notoriously difficult (Compare with Cramer's conjecture) and I do not expect this to be any easier. I will therefore not give a definitive answer, but rather try to give some heuristics. The Cramer model (see for example the paper of Granville "Harald Cramer and the distribution of prime numbers") where we assume that the probability that $n$ is prime is about $1/\log n$ gives that the probability that $k!+j$ should be prime should be about $1/\log(k!)$ which by Stirling's formula is about $1/k \log k$. This would give an average prime gap of about $k\log k$.

One might reason a little bit further. Of course when we consider $k!+j$ for $2 \leq j \leq k$ we have forced these number to be composite. In general the number $k!+j$ will be composite if some prime factor of $j$ is less than $k$. We may then ask what is the probability that the number $j$ has all prime factors greater than $k$? If $k < j < k^2$ this is true if and only if $j$ is prime which has probability about $1/\log j$ which if $k < j < k (\log k)^N$ is about $1/\log k$. One might then expect the probability that the number $k^2+j$ to be prime should be the product of these probabilities or $1/(k(\log k)^2)$.

However then we have not recognized the fact that we have forced the number $k!+j$ to have no prime factor less than $k$. This means that we should look at the conditional probability that an integer $n$ is prime given that it has no prime factors less than $k$. A simple sieving argument shows the number is odd should give us $1/2$ of the numbers, forcing that the number is not divisable by 3 should give us about $2/3$ of the numbers, and so forth. In general we should have about $$\prod_{p \le k} \left(1-\frac 1 p \right) \sim \frac{e^{-\gamma}}{\log k}$$ (By Merten's formula) numbers remaining after the sieving process. This is also suggested by the use of Dirichlet's theorem. This should give us the probability $e^{\gamma}/k \log k$ that the number $k!+j$ is prime, which is up to a constant the same as suggested by the Cramer model. In both cases the average prime gap can be expected to be of the order $k \log k$, albeit with different constants.

Answer by Johan Andersson for Function zeros in strip 0 < Re < 1

2010-11-13T13:52:29Z

The question for the case of a linear combination of Dirichlet L-series is actually easier than the case of a single L-function (Since RH is not known). In fact in each strip $1/2 \leq \sigma_1 <\Re(s)<\sigma_2 \leq 1$ there exists $\gg T$ zeroes for $-T < \Im(s) < T$. This follows by e.g. the Joint Voronin universality theorem for Dirichlet L-functions of Bagchi (A good reference for these results is Jörn Steuding's SLN 1877 "Value Distribution of L-functions").

Update Nov 14. I found the recent paper of Saias and Weingartner "Zeros of Dirichlet series with periodic coefficients", Acta Arithmetica 2009 where they get the same results that I indicated above, but also that there exists zeros to the right of the critical strip. Namely there exists some $\eta>0$ such that there are $\gg T$ zeros in any strip $1 \leq \sigma_0 <\Re(s) < \sigma_1 \leq 1+\eta$. This is actually simpler to prove since the Dirichlet series is absolutely convergent and the joint universality result is not needed, and more classical results of Bohr can be used instead.

Regarding zeros on the left of the critical line. The same result should hold in that in any vertical strip there exists $\gg T$ zeros. While this is not done in Saias-Weingartner as far as I can see it follows from the functional equation and using joint universality for the L-series in $1/2<\Re(s)<1$. Now we have two different functional equations depending on whether the L-series is odd or even it differs slightly in the Gamma-factors (this is the reason why the argument in my first answer is not applicable. See below). However Stirlings formula should imply that they do not differ sufficiently for this argument not to hold.

Further results we can get unconditionally is that there are about $T \log T$ with imaginary part less than $T$. It is not too difficult to prove that if we have a closed vertical strip that does not include the critical line, that the right order of magnitude actually is $T$, from which it would follow that for any open vertical strip including the critical line would have $T\log T$, i.e. the majority of the zeros, so the zeros should cluster around the critical line. Explicit results in this direction are included in the paper of Jörn Steuding "On Dirichlet series with periodic coefficients", Ramanujan Journal 2002 where he proves these results, i.e. clustering around $\Re(s)=1/2$, as well as other estimates (Another related paper is Garunkstis-Steuding "On the zero distribution of the Lerch zeta-function" where they prove corresponding results for the Lerch zeta function).

However to prove that they lie exactly on the critical line I believe that they must satisfy the same functional equation (see below) so an analogue of the Hardy function can be found and worked with. Therefore it is not clear (I am not sure about this though) that there should be any zeros exactly on the critical line (at least in order for there to be zeros on any particular line there should be a reason for it, since the zeros are countable, but the reals in an intervals are uncountable). Numerical experiments are welcome (I am not doing them though.).

Edit after comment of John below: I had originally thought that Bombieri and Hejhal's, and Hejhal's and Selberg's later results on linear combinations of L-functions would have applied on this problem, but as John pointed out below, this should not be the case, since the L-functions have to have the same Functional equation. Selberg's latest (unpublished) result would have yielded a positive proportion (order of $T \log T$ of zeros on the critical line), and Bombieri-Hejhal's (conditional on RH and weak Montgomery pair correlation conjecture) would have yielded the true asymptotics, if this would have been the case.

I checked one of Hejhal's papers on this subject, and John is right in his comment below. The condition to apply this method is that the Gamma-factors in the functional equation and the modulus are the same. When we consider a linear combination of Dirichlet L-functions we have to have a combination of only odd or even Dirichlet characters and the same modulus. For the Hurwitz zeta-function of rational parameters all Dirichlet characters will appear and thus this example is not of this type.

Thus I do not have an answer regarding zeros on the critical line. However the argument that shows that we have at least the order of $T$ zeros in any vertical strip $1/2 \leq \sigma_1<\Re(s)<\sigma_2 \leq 1+\eta$ with imaginary part less than $T$ still holds. Thus at least we know that Riemann hypothesis is not true for this function.

                                   Johan

Comment by Johan Andersson

2013-05-14T15:45:51Z

This does not seem to work since we do not longer know that $|f(c(1+i))|>|f(0)|$ after scaling with the constant $c$. By using the lagrange interpolation formula in a differnt way (as in my new answer above) to be say $1$ for $1,i,1+i$ etc and $0$ for $z=0$ and adding a sufficiently large positive constant $k$, we are sure that $0<p(0)<p(z)$ (and of course the same inequality holds when taking absolute values) when $z=1,i,1+i$, etc and also that the polynomial is zero-free.

Comment by Johan Andersson

2013-05-14T15:30:16Z

Actually if we consider the generalized problem of $n$ points $z_k$ and want to find a polynomial that is zero-free on a disc D such that $|f(0)|<|f(z_k)|$ a similar construction $p(z)=z^N+k$ works. First use Kroneckers approximation theorem to find $N$ such that $N \arg(z_k)$ mod $2 \pi$ lies in the interval $(-\pi/2,\pi/2)$. Then find $k$ sufficiently large such that the polynomial is zero free.

Comment by Johan Andersson

2013-05-12T17:33:34Z

unit disc was a mistake that I just corrected. Thanks, I meant the unit square. The same result holds however for the unit disc, for example for any closed Jordan domain with the inequality holding for finitely many boundary points.

Comment by Johan Andersson

2013-05-12T17:14:27Z

Gerald's answer is much better and simpler than my. I was considering deleting my answer, but decided to leave it.

Comment by Johan Andersson

2013-05-09T09:49:51Z

and by Stirling's formula this gives us $f(n)=\sqrt{2 \pi n} (\frac{n}{4e \ln n})^n (1+O(n^{-1/2}))$.

Comment by Johan Andersson

2013-04-14T19:25:35Z

See also the question and my answer mathoverflow.net/questions/45912/…

Comment by Johan Andersson

2013-04-14T19:20:46Z

The second reference should be Booker, Strömbergsson and Venkatesh, not just Venkatesh

Comment by Johan Andersson

2013-02-22T15:24:45Z

Koosis, The logarithmic integral part I has a good treatment of this theory (part II treats the somewhat more complicated Beurling-Malliavin theorem).

Comment by Johan Andersson

2013-01-14T15:13:42Z

In the first section I state that. In the second section I mention the analogue of the Davenport-Heilbronn theorem that there are zeroes for Re(s)>1. It should follow in a similar way as the case of the Hurwitz zeta-function for rational parameter.

Comment by Johan Andersson

2012-11-26T13:26:18Z

Mark, your conclusion that the number of primes less than x such that p-1 has a prime factor larger than $\sqrt(p)$ is asymptotic to x/(2ln(x)) is not correct. Note that we have a log(q) factor in the result not log(p) and for the relevant range of q we have $\log(p)/2 \leq \log(q) \leq \log(p)$ and they are not asymptotically equal. Greg is correct that the density should be $\log 2$.

Comment by Johan Andersson

2012-05-19T16:41:17Z

No, I do not think so. In fact if $\sup_{\zeta(s,N,a)=0}\Re(s)=c_1$ then $c_1>1$ and given any $c_0>1$ there will be $\gg T$ zeros in $c_0<\Re(s)<c_1$. These results follows from results of Bohr and Kronecker's theorem.

Comment by Johan Andersson

2012-05-19T16:19:43Z

That zeroes cluster around the cricital line is well-known phenomena, see for example my answer mathoverflow.net/questions/45912/…, where I cite a paper of Steuding that proves this result in the case of the periodic zeta-function (Your zeta-function $\Psi^*$ is such a function).

Comment by Johan Andersson

2012-05-10T21:07:18Z

This follows from the identity $\sum_d \mu(d) \sum_k f(d^2k)=\sum_n |\mu(n)| f(n)$ which follows from the fact that $\sum_{d^2|n} \mu(d)=|\mu(n)|$.

Comment by Johan Andersson

2012-05-10T18:48:22Z

@Dror, I have written an answer to your comment as another answer (does not fit as a comment) where I show that by combining the elementary and analytic method even better results can be obtained.

Comment by Johan Andersson

2012-05-09T14:05:44Z

@GH Heath-Brown (1980s) used sieve methods to improve on Huxley's result slightly, to show that $\theta=7/12$ is admissible. In fact he proved that we may choose $\theta=7/12-w(x)$ for any function such that $w(x)=o(1)$.