39

Your data is compatible with the more refined estimates proved by Vaughan in Ramanujan J. 15 (2008), 109–121. His Theorems 1 and 2 (together with his (1.9)) reveal that
$$\log(A000607(n)) = 2 \pi \sqrt{\frac{n}{3 \log n}}\left(1+\frac{\log\log n}{\log n}+O\left(\frac{1}{\log n}\right)\right). $$
For $n=50000$, we have
$$\log(A000607(n)) \approx 252.663 $$
$$...

22

I'll show that
$$
\log a(n) \sim \frac{(\log n)^2}{\log 4} \approx 0.7213\ldots (\log n)^2.
$$
So the range for the constant given in the conjecture is false, but an asymptotic of that general shape
holds. One can obtain more precise asymptotics by working harder with the argument below.
Roughly speaking what the argument says is that $a(n)$ behaves (...

21

For the asymptotic case: Let $t_1=n \log n - Cn$ and $t_2 = n \log n + Cn$, where $C$ is slowly tending to infinity. It is a classic result that as $C$ tends to infinity the probability all coupons are collected at time $t_1$ tends to $0$, and the probability all coupons are collected at time $t_2$ tends to $1$.
So the number being asked for in the ...

answered Aug 28 '15 at 20:24

Kevin P. Costello

5,25611 gold badge2121 silver badges3333 bronze badges

19

I sketch the arguments for $C(x)$, the arguments for $L(x)$ are essentially the same.
The specific form of the sum suggests probabilistic arguments.
Let $X_x$ be a $\mathrm{Poiss}(x^2)$-distributed random variable and note that
$$C(x)\,e^{-x^2}=\mathbb{E}\frac{x}{\sqrt{X_x}}\,1_{\{X_x\geq 1\}}$$
It is known that $\frac{X_x -x^2}{x}\longrightarrow N(0,1)$ (...

fa.functional-analysis ca.classical-analysis-and-odes real-analysis sequences-and-series asymptotics

19

The paper entitled Euler constant as a renormalized value of Riemann zeta function at its pole by Andrei Vieru contains a derivation of the first formula in the OP (Benoȋt Cloitre's formula), and a method to obtain variations thereof, such as
as well as similar iterates in terms of the Dirichlet function $\lambda(s)=\sum_{n=0}^\infty(2n+1)^{-s}$,

answered Dec 1 '19 at 20:58

Carlo Beenakker

107k99 gold badges252252 silver badges369369 bronze badges

18

In the main theorem of this recent paper of Pintz, Zhang's method is used to show that (for $k$ large enough), there are $\gg_{\mathcal H} \frac{x}{\log^k x}$ values of $n \le x$ such that two of the $n+h_i$ are prime and the remaining $n+h_j$ are almost prime (have $O_k(1)$ prime factors, all of which are $\gg x^{c_k}$ for some $c_k>0$ independent of $x$)...

answered Oct 20 '13 at 15:48

Terry Tao

74.3k2121 gold badges288288 silver badges372372 bronze badges

15

Since you mentioned Cayley's theorem for spanning trees, I believe one important example is its higher dimensional analogue due to Kalai. Indeed the number of simplicial spanning trees of the k-skeleton of an n-simplex is $$f(n)=n^{\binom{n-2}{k}} \implies \lim_{n\to \infty}\frac{\log\log f(n)}{\log n}=k.$$
Some further work has been done in this direction, ...

answered Dec 29 '14 at 0:43

Gjergji Zaimi

73.4k44 gold badges186186 silver badges340340 bronze badges

15

For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics" (see p.481) with the main ingredients being singularity analysis and the relation
$$I(z)=H(z)-\frac{1}{2}\left(H(z)^2-H(z^2)\right)$$
where $I$ is the ...

14

No, even in the most favorable case $(X_i)_{i\geqslant 0}$ iid with $\mathbb P(X_i=1)=\mathbb P(X_i=-1)=1/2$. Denoting $F_n$ the cumulative distribution function of $n^{-1/2}S_n$, we have by symmetry
$$F_{2n}(0)=\frac 12(1+\mathbb P(S_{2n}=0)).$$
Since $\mathbb P(S_{2n}=0)=\binom{2n}n2^{-2n}$, denoting $\Phi$ the cdf of the standard normal distribution,
$$\...

14

See Erick Wong's response here. In particular, Kevin Ford proved (in more precise form) that
$$ f(n) = \frac{n}{\log n} \exp\left(O(\log \log \log n)^2\right),$$
whence $f(n)/n$ tends to zero. The same consequence also follows from an earlier result of Pillai (1929), available online here.

14

The first formula is trivial. $$f(s)= \frac1{s-1}+\gamma +O(s-1)$$ $$g(z)=1+2^{-z}+3^{-z}+4^{-z}+O(5^{-z})=1+2^{-z}(1+(3/2)^{-z}+(4/2)^{-z}+O(5/2)^{-z})$$
$$f(g(z)) = \frac1{2^{-z}(1+(3/2)^{-z}+(4/2)^{-z}+O(5/2)^{-z})}+\gamma+O(2^{-z})$$ $$=2^z \left(1-(3/2)^{-z}-(4/2)^{-z}+O(5/2)^{-z}+(O(3/2)^{-z})^2\right)+\gamma + O(2^{-z})$$
$$=2^z- (3/4)^{-z}-1+O(9/8)...

13

Let us just consider the case $\alpha=2$ where there is an elegant answer: There exists a
constant $\lambda$ such that for all $n$ we have $u_n = \lceil \lambda^{2^n}\rceil$. First note that by induction it is easy to see that $u_n \ge (n+2)$ for all $n\ge 0$. Define
$$
\lambda= 2 \prod_{n=1}^{\infty} \Big(1-\frac{n}{u_{n-1}^2}\Big)^{\frac{1}{2^n}}.
$$ ...

13

This is a binary additive divisor problem (also known as the shifted convolution problem) and related questions are to understand asymptotics for $\sum_{n\le x} d(n) d(n+k)$, or $\sum_{n\le x} \lambda_f(n) \lambda_f(n+k)$ where $\lambda_f$ denotes the Fourier coefficients of a cusp form. For your particular problem, Ingham first showed the asymptotic ...

13

We can attack this problem by using Fourier transforms (i.e. characteristic functions). I'll consider
the example in the problem where $X$ is a random variable taking the value $0$ with probability $1/3$, and $4^{k}$ and
$-4^{k}$ with probability $1/4^{k+1}$ (for $k=0$, $1$, $\ldots$). I'll show that the probability that $|X_n|/n >M$ is
about a ...

12

I'll address Joel's edited question of getting good asymptotics on RH. The argument below is essentially due to Selberg, but this is not quite what he does and I haven't seen it presented this way in the literature. The natural problem is to consider the coefficients of $(\log \zeta (s))^k/k!$ rather than numbers with exactly $k$ prime factors. Note that ...

12

Gradshteyn & Ryzhik equation 3.773.1 gives (for $q>0$)
$$\frac{1}{q}B(q)=\int_0^\infty \frac{\sin x}{x(q^2/4+x^2)^{1/2}}\,dx=\frac{1}{q}G^{21}_{13}\left(\frac{q^2}{16}\biggl|^1_{1/2,1/2,0}\right)$$
$$\qquad\qquad=1-\gamma+\log 4-\log q+{\cal O}(q^2)=1.80908-\log q+{\cal O}(q^2).$$
The asymptotic result desired by the OP is $B(q)/q=\pi\gamma-\log q=1....

answered Feb 17 '16 at 15:09

Carlo Beenakker

107k99 gold badges252252 silver badges369369 bronze badges

12

The asymptotic formula is true for even dimensions $k\geq 2$. We can prove this by induction on $k$, inspired by Rodrigo's observation on Eisenstein series.
The case $k=2$ is classical and addressed in the OP's previous post that he linked. Now it suffices to show that if the formula is true for even dimensions $k,\ell\geq 2$, then it is also true for ...

12

The asymptotic you want does not hold just because the "last-term fluctuation"
$$ g(n)-g(n-1) = 2\sum_{a=1}^n \gcd(a,n)-n $$
is too large. Indeed, denoting the sum in the right-hand side by $\sigma(n)$, we have
$$ \sigma(n) =\sum_{d\mid n} d\varphi(n/d) = n \sum_{d\mid n} \prod_{p\mid(n/d)} \Big(1-\frac1p\Big) = n \sum_{d\mid n} \prod_{p\mid d} \Big(1-\...

11

Write $V(a)$ for the determinant $\prod_{0\leq i<j\leq n-1} |a_i-a_j|$. Selberg's formula tells you that
$$\int_0^1 \cdots \int_0^1 V(a)^{2\beta} \prod_{i=0}^{n-1} da_i=
n! \prod_{j=0}^{n-1} \frac{(\Gamma(1+j\beta))^2 \cdot \Gamma((j+1)\beta)}
{\Gamma(2+(n+j-1)\beta)\cdot \Gamma(\beta)}=:A(n,\beta)$$
Thus the asymptotics you seek are given by $\lim_{\...

ca.classical-analysis-and-odes oc.optimization-and-control asymptotics determinants legendre-polynomials

11

It is not hard prove the bounds you want by purely real variable techniques. First note that the $a_n$ are non-negative for all $n$. For a general non-negative sequence $a_n$, and real numbers $N>0$, put
$$
F(N) = \sum_{n=0}^{\infty} a_n e^{-n/N},
$$
and assume that there are constants $\alpha >1$, and positive constants $c_1$ and $c_2$ such that ...

11

We may just write down $\varphi(k)=k\cdot \prod_{p|k} (1-1/p)$, $p$ runs over the primes which divide $k$, then
$$
\frac{\left(\prod_{k\leqslant n}\varphi(k)\right)^{1/n}}{n}=\frac{\sqrt[n]{n!}}n\prod_{p} (1-1/p)^{\frac{[n/p]}{n}}.
$$
First multiple tends to $1/e$ by weak version of Stirling's formula, and in the product we may replace each exponent $\frac{[...

11

I think your final goal follows by taking the logarithmic derivative of the functional equation:
$$\frac{\zeta'}{\zeta}(s)+\frac{\zeta'}{\zeta}(1-s)=\log\pi-\frac{1}{2}\frac{\Gamma'}{\Gamma}\left(\frac{s}{2}\right)-\frac{1}{2}\frac{\Gamma'}{\Gamma}\left(\frac{1-s}{2}\right).$$
Applying this with $s=it$ and using the familiar asymptotic expansion of $\Gamma'/\...

11

The answer is no, even in the smooth case. Take for example:
$$
f(x) = \frac{2}{x} + \frac{\cos(\log(x))}{x}
$$
Alter it on a small neighborhood of $0$ in such a way that there is no singularity there, preserving smoothness (this will be irrelevant for the asymptotics). This function is decreasing and, for $t$ sufficiently large, we have
$$
\int_0^t f(x) ...

11

$\newcommand{\ep}{\varepsilon}
$
Let $X$ be any nonnegative random variable (r.v.) with finite mean $\mu>0$ and variance $\sigma^2<\infty$. For any real $u>0$, we have $\ln\frac xu\le\frac xu-1$ for all real $x>0$, whence
$x\ln x\le\frac{x^2}u+x\ln\frac ue$ and
\begin{equation*}
EX\ln X\le\frac{EX^2}u+EX\ln\frac ue=\frac{\sigma^2+\mu^2}u+\mu\...

10

Uniformity on compact sets interior to the domain
The boundary condition has no real impact on the small-time asymptotics of the heat kernel for interior points. More precisely, consider a Riemannian manifold $\mathbb{M}$ and $\Omega$ a relatively compact smooth open domain in $\mathbb{M}$. Denote by $p_\Omega$ the heat kernel associated with a self-...

10

De Bruijn's "Asymptotic methods in analysis" is an excellent book for beginners. You'll need to work through it diligently to learn everything but no advanced a priori knowledge is required. Also, you can easily download it from many online places that do not worry too much about copyright and, even if you decide to stay law-abiding, it goes for under ten ...

10

I don't think a nice asymptotic formula like the one you've mentioned from Tutte's work is available for higher $g$ to the best of my understanding; it is entirely possible that someone who regularly deals with such things will come along and show us otherwise.
Meanwhile, the state-of-the-art on counting triangulations of genus $g$ surfaces is the lovely ...

10

Assuming that $|x+y|<1$ and $4|xy| \le 1$, here's a proof of the decay.
First suppose that $|x|> |y|$. The desired sum is
$$
\le \binom{2n}{n} |xy|^n \sum_{j=0}^{n} |y/x|^j \le
\binom{2n}{n} |xy|^n \frac{1}{1-|y/x|}.
$$
Since $\binom{2n}{n}$ is of size about $4^n/\sqrt{n}$, the desired decay follows in this case.
Next suppose $|x| <|y|$. ...

10

Let $A(x)$ denote the formal generating function of $\{ a_n\}$. The recurrence relation can be written as $A(x)=e^x A(x^2)$. Applying this repeatedly, we find $A(x) = e^x e^{x^2} \cdots = e^{f(x)}$, where $f(x) = \sum_{i \ge 0} x^{2^i}$.
Asymptotics of $[x^n] e^{P(x)}$ where $P$ is a polynomial with positive coefficients are "easy", for example they follow ...

10

OK, let's see if I can put my money where my commenting mouth is. Let me say at the outset that I have no idea where such an integral comes from, but I claim that it doesn't matter to answer the question.
First of all, $\mathbf e$ is nothing mysterious: it is the 2-form dual to a hyperplane section of $M$. The equation $\int_M \mathbf e^3=5$ is just a fancy ...

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

#### Related Tags

asymptotics × 658co.combinatorics × 129

nt.number-theory × 124

pr.probability × 108

ca.classical-analysis-and-odes × 86

real-analysis × 78

analytic-number-theory × 76

sequences-and-series × 53

reference-request × 47

probability-distributions × 40

special-functions × 39

cv.complex-variables × 35

inequalities × 35

prime-numbers × 34

binomial-coefficients × 34

integration × 31

fa.functional-analysis × 25

st.statistics × 23

differential-equations × 18

limits-and-convergence × 17

fourier-analysis × 16

hypergeometric-functions × 14

ap.analysis-of-pdes × 13

random-matrices × 13

approximation-theory × 13