Questions involving asymptotic analysis, including growth of functions, Big-O notation, Big-Omega and Big-Theta notations.

learn more… | top users | synonyms (1)

11
votes
0answers
367 views

Asymptotic related to the infinite product of sine

The amount is somewhat complicated ($x$ is a constant): $$S_n=\sum_{k=1}^n\ln\left(1-\frac{\sin^2\big(x/(2n+1)\big)}{\sin^2\big(k\pi/(2n+1)\big)}\right)\tag{*}$$ I want to enrich my handy powerful ...
8
votes
0answers
117 views

Integral Asymptotics for inhomogenous phase

I'm looking for asymptotics for an integral of the form: $$F(n):=\int_{1/2-i\infty}^{1/2+i\infty} e^{\phi(n,z)}dz$$ where $\phi(n,z)=(n-n^3)\log(1-z)+n^2\log(1+z)-n\log(z)$. One can solve for the ...
8
votes
0answers
99 views

Given the first $n$ primes, find the least common multiple of $p_1 - 1$, $p_2 - 1$, …, $p_n - 1$

Given the first $n$ primes, we can label the $k$th prime as $p_k$. So, what is the least common multiple(LCM) of {$p_1 - 1$, $p_2 - 1$, $p_3 - 1$, ..., $p_n-1$}? In other words, if we subtract $1$ ...
8
votes
0answers
159 views

Let $x_n$ be the (unique) root of $\Delta f_n(x)=0$. Then $\Delta x_n\to 1$

Note that by Cesaro's Theorem, we have as a consequence $$\frac{x_n}n\to 1$$ Consider $$r_n(x)=e^{-x}-\sum_{k=0}^n (-1)^k\frac{x^k}{k!}$$ and $$f_n(x)=(-1)^{n+1}e^{-x}r_n(x)$$ One can argue by ...
8
votes
0answers
185 views

An integration to first order

I am having some trouble evaluating an integral -- involving taking an approximation. It would be great if someone could help me. I wish to evaluate $$\int_0^\pi {\cos\theta\cos \left[\omega ...
7
votes
0answers
43 views

Decay of amplitude integral

Consider the function $$ f(\vec{x}) = \int_{\Bbb R^3} {\frac{ e^{-i\,\vec{x}\cdot\vec{k}}}{\sqrt{\vec{k}^2 + m^2}}} d^3 k $$ from Zee's Quantum Field Theory in a Nutshell. He argues like this: ...
7
votes
0answers
144 views

Is it true that $\gamma_{\lfloor\log\Gamma(x)\rfloor}\sim 2\pi x$?

I realise that Gram points can approximate the imaginary part on the $x$th zeta zero $(\gamma_x)$ accurately, and indeed, Guilherme França, André LeClair give another formula, namely ...
7
votes
0answers
238 views

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
7
votes
0answers
76 views

Partitioning points with a line

Let $A_{m, n} = \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$. A straight line would partition the points into two sets. How many ways are there to do it? Let $p_{m, n}$ be that number. Apparently ...
6
votes
0answers
48 views

Show that $1^k+2^k+…+n^k$ is $O (n^{k+1})$.

Let $k$ be a positive integer. Show that $1^k+2^k+...+n^k$ is $O (n^{k+1})$. So according to the definition of big-$O$ notation we have: $$1^k+2^k...+n^k ≤ n(n^k) = n^{k+1}$$ whenever $n>1$ Is ...
6
votes
0answers
120 views

Asymptotic behavior a recursion involving min/max

Usually when I face solving recursions I use generating functions but I'm not aware of any "tools" to use when min/max expressions are involved. For example, I have the following recursive term: ...
6
votes
0answers
92 views

Asymptotic property of integral involving Bessel function.

Consider the following integral $$ I(s)=\int_{0}^{\infty}{J_{\frac{n-2}{2}}}(sr)r^{A+1}(e^{-r^{2\alpha}}-1)dr, $$ where $J_{\frac{n-2}{2}}$ is the Bessel function of order ${\frac{n-2}{2}}$, $s, A, ...
6
votes
0answers
205 views

Hints/Help studying an Abel Differential Equation

I want to know more than qualitative information about the Abel differential equation $\frac{dy}{dx}+y^3+x=0$. $\qquad ... \;(1)$ Since I don´t know how to solve this and as far as could see, this ...
6
votes
0answers
249 views

Sums of Dirichlet-Characters over prime numbers (part 2)

This is kind of related to my previous question that was poorly stated because of misreading my own notes that I have taken on the papers I am currently reading, so no surprise that it eventually ...
5
votes
0answers
96 views

Boundary Layer, leading order, Pertubation Theory, Differential Equations

I have got the following problem, taken from Multiple Scale and singular perturbation methods, Kevorkian & Cole book, page 94, exercise 1.b.: Find the leading order of the problem: $\varepsilon ...
5
votes
0answers
56 views

Singularities at roots of unity

I want to construct a function $f$ with the following properties: $f$ has a singularity at $z=1$, and for any $\zeta = e^{2\pi i\frac{a}{b}}$ with $(a,b)=1$, then $$\lim\limits_{x\to1^-}\frac{f(\zeta ...
5
votes
0answers
120 views

Asymptotic expansion of $\zeta(s)$

It is well known that $$ \zeta(s) = \sum_{n = 1}^\infty \frac{1}{n^s} = \prod_{p \text{ prime}} \frac{1}{1 - p^{-s}}, \quad \Re[s] > 1, \tag{1}$$ but, if $p \leq N$ denotes the primes less than or ...
5
votes
0answers
103 views

Binomial asymptotic.

Is there any "direct" proof of the following asymptotic inequality: let $\alpha\le 1$ and consider $$Q_n(x)=\sum_{k=1}^n\frac{\alpha(\alpha+1)(\alpha+2)\cdots(\alpha+k-1)}{k!}x^k$$ Then, $$\int_0^1 ...
4
votes
0answers
65 views

Growth of $n!!\dots !$

The asymptotic growth of the factorial function $n!$ is famously given by Stirling's formula as $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ Is there a similar formula for the iterated ...
4
votes
0answers
54 views

A general question of asymptotics

I am very desperately longing to know if there is a explicit relationship between $$F(n)=f(1)+f(2)+...+f(n)$$ and $$G(x)=\sum_{k=1}^{\infty}f(k)x^k$$ Assuming we can let $f$ be a sufficiently well ...
4
votes
0answers
66 views

Looking for a closed form for the quotient of a sequence of compositions of $\exp()$-function

Related to that previous question I have another still open detail problem. Consider the sequence of evaluations at some given $x$ $$ \small \begin{array} {} z_0 &=& e^x \\ z_1 ...
4
votes
0answers
219 views

Question about Big O notation for asymptotic behavior in convergent power series

Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page. The idea, as I understand it, is that the term between parenthesis in Big O ...
4
votes
0answers
63 views

Asymptotics for Mertens function

It seems that the cumulative mean of the Mertens function is very similar in behaviour to $x$ raised to the power of the first zeta zero. I tentatively notate it as: ...
4
votes
0answers
91 views

Prove that a series is $O(t^a)$.

Consider the series $$ u(t,x) = \sum_{i \geq 1} {u_i(x) t_1^i } + \sum_{i+2j \geq k+2, j\geq 1} {\varphi_{i,j,k}(x) t_1^i t_2^j y^k} $$ where $t \in \tilde{\mathbb{C} \setminus \{ 0 \}}$, $x$ is ...
4
votes
0answers
162 views

How many edges does an Erdős-Rényi graph have to have, to almost surely have a component with multiple cycles?

An Erdős-Rényi graph is a random graph, selected according to the distribution obtained one where we have some number $n$ of nodes, and some probability $p$ of each potential edge being ...
4
votes
0answers
255 views

An entire function of strict order 2

Here is a problem from Stein and Shakarchi Complex Analysis, can somebody help me to solve it? I guess we can use Phragmen-Lindelof theorem but I don't know the exact way. Suppose $f(z)$ is an entire ...
4
votes
0answers
172 views

Understanding Newman's proof of the prime number theorem

I am trying to understand D.J. Newman's proof of the prime number theorem, as presented by D. Zagier. I am not too familiar with analysis, and so there are some things I don't understand. In (III), ...
4
votes
0answers
77 views

Dominated convergence on $e^{-n^2 t} t^{s/2-1}$

I am trying to apply the Dominated Convergence Theorem to show that $$\sum_{n\ge 1} \int_0^1 e^{-n^2 t} t^{s/2-1}dt= \int_0^1 \sum_{n\ge 1}e^{-n^2 t} t^{s/2-1}dt$$ as soon as $s>1$. I've ...
4
votes
0answers
505 views

When do floors and ceilings matter while solving recurrences?

I came across places where floors and ceilings are neglected while solving recurrences. Example from CLRS (chapter 4, pg.83) where floor is neglected: Here (pg.2, exercise 4.1–1) is an example ...
4
votes
0answers
235 views

How fast does $\binom{n}{k}$ grow when $k \le n/2$?

How fast does $\binom{n}{k}$, $n$ fixed, grow when $k \le n/2$? Especially, I'm interested in the growth of the "inverse" of binomial coefficient $B_n(x) := \min \{k:\binom{n}{k} \ge x\}$. EDIT: ...
4
votes
0answers
104 views

Asymptotic Analysis of Complex Integrals

Let $\gamma\subset B(0,2)\subset \mathbb{C}$ a smooth Jordan curve envolving the origin and $\phi:\mathbb{C}\setminus (-\infty,0)\to \mathbb{C}$ an analytic function having finite boundary values, ...
3
votes
0answers
17 views

Big-O Notation exponentials

I'm learning about Big-O notation for algorithm runtime, and I need some help understanding one part. I read that for the constant, c, does not matter as the function increases rapidly. Does that ...
3
votes
0answers
41 views

Asymptotic expansion of a Fourier Transform as $\omega\rightarrow 0$

First of all, I do apologise if the question is not formulated in precise mathematical terms, but as a physics student I lack a formal background on rigorous functional analysis. Suppose we have a ...
3
votes
0answers
35 views

Merten's function

I am tasked with applying the Wiener-Ikehara Theorem to achieve a bound of little o(x) on Merten's function $\sum_{n=1}^x \mu (n)$. My problem is the Wiener-Ikehara Theorem applies to Dirichlet series ...
3
votes
0answers
36 views

Applying function to both sides of asymptotic expression

I apologize in advance if this has been asked elsewhere, but I couldn't find it. This seems like it should be a pretty simple question, but I'm drawing a blank. If you know that $f(x) \sim g(x)$, ...
3
votes
0answers
33 views

Proof $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$

There is an exercise that ask me to prove this logic formula about the complexity of algorithms: $\mathcal{O}(f(n)) = \mathcal{O}(g(n)) \iff f(n) \in O(g(n)) \land g(n) \in \mathcal{O}(f(n))$ ...
3
votes
0answers
40 views

How does the Stokes phenomenon appear in the asymptotic expansion of $\int_0^\infty \frac{e^{-zt}}{1+t^4} dt$ for $z \to \infty$?

Consider the asymptotic $z \to \infty$ behaviour of the function $$ \tag 1 I_1(z) \equiv \int_0^\infty \frac{e^{-zt}}{1+t^4} dt.$$ This converges for $\Re(z) > 0$, and the asymptotic expansion $$ ...
3
votes
0answers
83 views

How can one derive Stokes lines of the Stokes phenomenon of asymptotics from a differential equation?

Is there a standard technique to calculate Stokes lines and anti-Stokes lines of the Stokes phenomenon of asymptotics for a function defined as the general solution to a differential equation without ...
3
votes
0answers
32 views

Computing the asymptotic spectrum of a negative distance kernel

Consider the following integral operator: $$K(f) : x \mapsto\int_0^1 K(x,x')f(x') dx', \quad \text{where} \quad K(x,x') = - |x-x'|^{3/2}.$$ The kernel is sometimes referred to as a negative ...
3
votes
0answers
81 views

Saddle point method: a rigorous proof?

I am trying to prove in a fully rigorous way the Saddle Point method for holomorphic functions of 1 complex variable. In books I find only complicated general statements or non-rigorous proofs. Hence ...
3
votes
0answers
99 views

WKB and asymptotic behavior of second order differential equation

I want to study the large $x$ solution to a Riccati equation. After listening to the lectures on Mathematical Physics by Carl Bender, I have fallen in love with asymptotic analysis. But, by no means ...
3
votes
0answers
70 views

Which series of numbers effectively translates the factorial to the exponential function?

We have the relation of the Bernoulli numbers $$B_{2n} = (-1)^{n+1}\frac {2(2n)!} {(2\pi)^{2n}} \left(1+\frac{1}{2^{2n}}+\frac{1}{3^{2n}}+\cdots\;\right).$$ For $n>1$, the right hand sum ...
3
votes
0answers
78 views

Asymptotics of partitions in at most n parts, bounded by r

For every positive integers $n,r,w$ define $$ p_w(n,r)=\#\{ (i_1,...,i_r) | \, 0\leq i_1 \leq \dots \leq i_r\leq n, \, i_1+\dots+i_r=w\} $$ as the number of partitions of $w$ in at most $r$ piece ...
3
votes
0answers
44 views

Growth rate of $\exp(log^{a}(x))$ slower then any power of $x$.

So I'm trying to show that for $0<a<1$ and for $\epsilon >0$ that $\exp((\log x)^{a})=\mathcal{O}(x^{\epsilon}).$ So this amounts to showing that ...
3
votes
0answers
88 views

Asymptotic solution for $T(n) = 6T(n/4) + n \lg n$

I am given that $T(n) = 6T(n/4) + n \lg n$ and want to find $\Theta(T(n))$. Below is what I have typed up for my solution so far; I asked my professor because I was unsure as to how I could assure ...
3
votes
0answers
57 views

Verifying an integral identity related to asymptotic homogenization of an elliptic partial differential equation

Background I'm reading Hornung (1997)'s Homogenization and porous media, pg 3: We study a family of [1D] problems, indexed by the scale parameter $\epsilon=\frac{1}{n}$, namely, ...
3
votes
0answers
110 views

Exponentials of chi-squared random variables (and their sums)

Let $X_1,X_2,\ldots,X_n$ be a sequence of i.i.d. chi-squared random variables with $t$ degrees of freedom, i.e. $X_i\sim\chi^2_t$. I am wondering what is known about the distribution of ...
3
votes
0answers
67 views

Limit of a sum (no probabilities)

Show that $$\lim_{n\to+\infty}\left(\frac{2}{3}\right)^n\sum_{k=0}^{[n/3]}\binom{n}{k}2^{-k}=\frac{1}{2}$$ without using probabilities. $[\;\cdot\;]$ denotes the integer part.
3
votes
0answers
76 views

Definition of small $o$

In one of my homework assignments (in intro to applied mathematics) there is the following definition: Given two functions $f(\epsilon),g(\epsilon)$ that are defined in $D=(0,\epsilon)$ we say ...
3
votes
0answers
169 views

Saddle point and stationary point approximation of the Airy equation

Happy New Year to you all. Let $$\tag 1 J(N)=\int_a^b e^{Nf(x)}dx$$ where $N\in\mathbb R$ and $N>>1$ and $f(x)$ has a global maximum at $x=x_0$ with Taylor expansion $$f(x) \approx ...