# Tag Info

53

If the Riemann zeta function had only trivial zeroes, then after multiplying by the gamma factor, it would become a zero-free entire function of finite order. Every zero-free entire function of finite order is of the form $\exp(poly(z))$. This cannot happen for the zeta function, as can be seen by considering behavior as $s\to\infty$ along the reals, for ...

42

It seems to be the case that the polynomial $P_n(x) =\sum_{m=1}^n m!S(n,m)x^m$ has only real zeros. (I know it is true that $\sum_{m=1}^n S(n,m)x^m$ has only real zeros.) If this is true, then the value of $m$ maximizing $m!S(n,m)$ is within 1 of $P'_n(1)/P_n(1)$ by a theorem of J. N. Darroch, Ann. Math. Stat. 35 (1964), 1317-1321. See also J. Pitman, ...

28

Here's a variation on the arguments using the explicit formula. If there were no zeros in the critical strip then the explicit formula would say $$\psi_0(x) = x - \frac{\zeta'(0)}{\zeta(0)} - \frac12 \log(1-x^{-2}),$$ where $\psi_0(x)$ is the same as the usual $\psi(x)$ except when $x$ takes integer values $\psi_0(x)$ is the average of the left and right ...

23

An intuitive reason is indicated by Bukh in another answer. The reason there are nontrivial zeros is because the zeta-function is known to grow in a way that it wouldn't grow if there were no nontrivial zeros. Here is some additional (but not complete) detail. Let's pass from the zeta-function to the completed zeta-function $$Z(s) = ... 21 (I've just typed a comment but somehow it got lost. I'll type an answer instead). Bloom is right, no zeros implies too nice a formula, except the right approximation to \pi(x) is \int_2^x dt/\log t, not x / \log x. The existence of zeros implies that the error cannot be better than O(x^{1/2}). On the other hand, the zeta function of ... 18 Rather than the problem of why the zeta function has non-trivial zeros, let me address Gowers's question of why the error term in the prime number theorem needs to be large. The short answer that I propose is: because the integers are so well distributed. To make this precise, I shall prove a general result on semigroups, showing that either the ... 15 This is part of topological dynamics (a close cousin of ergodic theory, aka measurable dynamics, in which the underlying space on which the dynamics takes place is a topological space rather than a measure space). The relationship with combinatorics is roughly as follows: topological dynamics is to colouring Ramsey theorems (such as van der Waerden) as ... 14 This reference contains the best result of this kind currently known for \mu(n): Tadej Kotnik and Herman te Riele The Mertens Conjecture revisited. Algorithmic number theory, 156--167, Lecture Notes in Comput. Sci., 4076, Springer, Berlin, 2006. They prove that \limsup_{x \rightarrow +\infty}M(x)/\sqrt{x} \geq 1.218 and that \liminf_{x \rightarrow ... 13 You probably know this, but: Set s(n) = \mu(1) + \cdots + \mu(n). Suppose, for the sake of contradiction, that s(n) = O(n^{1/2 - \epsilon}). Then$$\sum s(n) \left( n^{-s} - (n+1)^{-s} \right)$$would converge for Re(s) > 1/2-\epsilon. This would give an analytic extension of 1/\zeta(s) to this half plane, contradicting that \zeta has zeroes on ... 11 The idea (from the Selberg-Delange) method to doing this problem is the following steps: 1) Let F(s) = \sum_{n\ge 1} \frac{1}{n^s d(n)} = \prod_{p} \left(1 + \sum_{k=1}^{\infty} \frac{1}{(k+1) p^{ks}} \right). The latter is by multiplicativity of d(n). 2) If we look, instead at G(s) = \prod_p \left( 1 + \frac{1}{2 p^s} \right) we can see that ... 10 May I offer an attempt at a very lowbrow answer? This answer might naturally strike anyone who knows the functional equation, who looks at a color coded graph of zeta function such as http://en.wikipedia.org/wiki/File:Complex_zeta.jpg, and who knows a little about the long-range behavior of exponential functions and \Gamma(z). Nothing I will say is ... 10 For t fixed, the count is proportional to \lambda^n, where \lambda = 2 \cos \frac\pi{2t+2} is the principal eigenvalue of the adjacency matrix of the path with 2t+1 vertices. The all-positive (Perron-Frobenius) eigenvector corresponding to \lambda is$$\bigg(\sin \frac{\pi}{2t+2}, \sin \frac{2\pi}{2t+2},\sin \frac{2\pi}{2t+2},\dots,sin ...

9

(edited) The answer can be extracted from a paper of Ramanujan, "Some formulae in the analytic theory of numbers", no. 17 in his collected papers. There he gives, among other things, the formula $\sum_{n\leq X} \frac{1}{d(n)} \sim \frac{X}{\sqrt{\log{X}}}\pi^{-\frac{1}{2}}\prod_{p}\sqrt{p^2-p}\log{\frac{p}{p-1}}$. The answer to the original question can ...

9

This looks like the Stirling numbers of the second kind (up to the $m!$ factor). This and this papers are specifically devoted to the maximal Striling numbers. It seems that for large $n$ the relevant asymptotic expansion is $$k! S(n,k)= (e^r-1)^k \frac{n!}{r^n}(2\pi k B)^{-1/2}\left(1-\frac{6r^2\theta^2 +6r\theta+1}{12re^r}+O(n^{-2})\right),$$ where ...

9

Update 2: Original answer below. I've put together graphs showing more than just champions, using every $N\leq 10^4$ and also every $N\equiv 0\pmod{100}$ up to $10^5$. This is for the original version, not the variant, but I'd expect that to be essentially the same. I am starting to be somewhat skeptical of my $1/3$ estimate. I'll collect some data ...

8

Richard's answer is short, slick, and complete, but I wanted to mention here that there is also a "real variable" approach that is consistent with that answer; it gives weaker bounds at the end, but also tells a bit more about the structure of the "typical" surjection. I'll write the argument in a somewhat informal "physicist" style, but I think it can be ...

8

I found this paper of Temme (available here) that gives an explicit but somewhat complicated asymptotic for the Stirling number S(n,m) of the second kind, by the methods alluded to in previous answers (generating functions -> contour integral -> steepest descent) Here's the asymptotic (as copied from that paper). One first sets $t_0 := \frac{n-m}{m}$ and ...

8

If f is an arbitrary surjection from N onto M, then we can think of f as partitioning N into m different groups, each group of inputs representing the same output point in M. The Stirling Numbers of the second kind count how many ways to partition an N element set into m groups. But this undercounts it, because any permutation of those m groups defines a ...

8

Here are some other comments in the spirit of Terry's and Anton's answers. There is nothing special about the symbols $\pm 1$ in the question; the spaces of binary strings $(\mathbb{Z}/2)^\mathbb{N}$ and $(\mathbb{Z}/2)^\mathbb{Z}$ are a more standard notation. As Terry says, you can switch between singly infinite and doubly infinite sequences. The ...

6

If you apply the greedy algorithm, that is very close to asking for the maximum drawdown of a random walk with positive drift. The distribution of maximum drawdowns of a Brownian motion with constant drift have been studied, and some answers are on page 2 here. The expected maximum drawdown with positive drift grows asymptotically like $c \log M$. I'm not ...

6

Here is a useful supplement and references to the existing answers. I asked Yuval Peres a few days ago the question formulated as follows: What is the probability that the simple random walk of n steps will be confined to the interval $[-K,K]$? Yuval's answer a few hours later was: The confinement probability in [-K,K] decays up to a ...

5

Here is a plot of rlo's data (as listed in his/her item (1)):            And here is the $\log D(N) / \log N$ ratio he mentioned in the comment (where the constant red line is $\frac{1}{3}$):

5

I don't have a precise reference for your problem (given $n$ find "the most surjected" $m$); waiting for a precise one, I can say that I think the standard starting point should be as follows. To avoid confusion I modify slightly your notation for the surjections from an $n$ elements set to an $m$ elements set into $\mathrm{Sur}(n,m).$ One has the ...

5

As a matter of fact, it isn't hard to construct a multiplicative sequence $a_n$ such that $f(z)$ is an entire function without zeroes. Unfortunately, it is completely useless for the questions that you brought up as "motivation". Here is the construction. Claim 1: Let $\lambda_j\in [0,1]$ ($j=0,\dots,M$). Assume that $|a_j|\le 1$ and ...

5

This paper shows that $L(n) > .061867\sqrt{n}$ for infinitely many $n$. As for somewhat elementary methods (in the sense of avoiding the Riemann zeta function) to show that $L(n)$ is "usually" of order $\sqrt{n}$, one can use the Lambert series $$\sum_{n=1}^{\infty}{\frac{\lambda(n)q^n}{1-q^n}} = \sum_{n=1}^{\infty}{q^{n^2}}.$$ As \frac{q^n}{1+q^n} = ...

5

"Quasiperiodic" means that there is a function $L:\mathbb N\to\mathbb N$ such that any sequence of length $\ell$ appears in any sequence of length $L(\ell)$. You can get a quasiperiodic sequence as a limit, but you you will not get more. The later follows from your remark (which is added later). P.S. If you start with a quasiperiodic sequence, then you can ...

4

Here is a largely historical remark: Littlewood showed that there exists $x$ so that $\pi(x)$ is greater than the log-integral $\mathrm{li}(x)$. In fact, $\pi(x) - \mathrm{li}(x)$ is (more or less) a linear combination of factors $x^{1/2+it}$, where $1/2+it$ are zeroes of $\zeta$. Form the multiplicative convolution with a suitable smooth function: you ...

3

Every morphism $M\to G$ into a group factors through the group completion $\hat M$ (a.k.a. Grothendieck construction) of $M$. It follows that $G$ is a quotient of $\hat M$ and that $f$ factors through $\hat M$. If $f$ is an arbitrary function, I don't think you can get any information about the structure of $G$, except that it is a quotient of $\hat ... 2 As a lazy heuristic, one can consider the following construction. Consider the following operation$F$on sequences. Given a sequence$S$, we identify in$S$the first place$q$where the partial sum leaves$\pm t$. We identify the last place$r$preceding$q$in which it remains within$\pm t/2$. Then we let$F(S)$be the sequence obtained from$S$by ... 2 This might not be exactly what you have in mind, but it is an old result of Paley that for an infinite (but very sparse) set of real Dirichlet characters the inequality$max_{N} |\sum_{n}^{N} \chi(n)| > c \sqrt{Q} \ln\ln(Q) \$ holds, where Q is the modulus of the character. Montgomery and Vaughan have shown the reverse inequality (on RH) for all ...

Only top voted, non community-wiki answers of a minimum length are eligible