Questions tagged [asymptotics]

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

1,741 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18
votes
0answers
411 views

The Complexity of “The Baby Shark Song”.

This question is just for fun. I hope it's received in the same goofy spirit in which I wrote it. I just had the pleasure of reading Knuth's "The Complexity of Songs" and I thought it'd be hilarious ...
14
votes
1answer
213 views

Eigenvalue problem for $−\psi''(x) − (ix)^ N \psi(x) = E\psi(x)$ in complex plane

To find the eigenvalue $E$ in the complex plane of $x$ for one dimensional Schrodinger equation $$ −\psi''(x) − (ix)^ N \psi(x) = E\psi(x). $$ where $N$ can be any real number, the boundary condition ...
14
votes
0answers
551 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 ...
13
votes
0answers
196 views

Lower Bound on Oscillatory Integral

Let $p,y\in\mathbb{R}^d\setminus\{0\},\beta>0$ be given and fixed and define for all $\alpha>0$, $$I(\alpha) := \int_{x\in\mathbb{R}^d}\exp(\mathrm{i}\alpha p\cdot x-\alpha\beta \|x-y\|^2)f(x)\...
13
votes
0answers
241 views

Number as the sum of digits of some degree

We will say that the measure of a number is equal to the maximum degree in which it is possible to represent a number in the form of a sum of digits copied (You can not rearrange the numbers). For ...
13
votes
0answers
313 views

Asymptotics of Sums

Suppose $f(x)$ is a function such that $f(x)=O(x)$, then $$\sum_{n\leq x} f\left(\frac{x}{n}\right) =O\left( \sum_{n\leq x} \frac{x}{n}\right) = O\left(x\sum_{n\leq x}\frac{1}{n} \right) = O\left( x\...
13
votes
1answer
316 views

Upper bound for the widest matrix with no two subsets of columns with the same vector sum

Over at PPCG there is an ongoing contest going on to find the largest matrix without a certain property, called property $X$. The description is as follows (copied from the question). A circulant ...
12
votes
0answers
2k views

Does the “prime ant” ever backtrack?

A few mathematical questions have come up from the question "The prime ant 🐜" on the Programming Puzzles & Code Golf Stack Exchange. Here is how the prime ant is defined: Initially, we have ...
12
votes
0answers
192 views

Strong upper bound for consecutive p-smooth numbers

Størmer's Theorem provides a method to find all consecutive p-smooth numbers. In Lehmer's paper On a problem of Størmer, a very weak upper bound is given (Theorem 7). M. F. Hasler observes at A002072 ...
12
votes
0answers
186 views

Is almost any group generated by two generators?

What is the asymptotic probability that a randomly chosen finite group can be presented with $2$ generators? More precisely, what is $$ \lim _{n \to \infty} \frac{\text{number of 2-generated groups of ...
12
votes
0answers
391 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 t-{\...
11
votes
0answers
271 views

If $X_i∼fλ$, $Z∼\mathcal N(0,I_d)$ and $Y=X+\ell d^{-α}Z$ with $α<1/2$, then $\liminf_{d→∞}\text E\left[1∧\prod_{i=1}^d\frac{f(Y_i)}{f(X_i)}\right]=0$

Let $f\in C^3(\mathbb R)$ be positive $g:=\ln f$ $d\in\mathbb N$, $$p_d(x):=\prod_{i=1}^df(x_i)\;\;\;\text{for }x\in\mathbb R^d$$ and $\lambda^d$ denote the Lebesgue measure on $\mathcal B(\mathbb R^...
11
votes
0answers
229 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 $$\dfrac{2\pi(x-\...
10
votes
0answers
308 views

Let $|A|=|B|=|C|=n$ be three finite sets of integers. Find $\min |\{ab+c \mid a \in A, b \in B, c \in C\}|$.

For a triple of sets of integers $A,B,C$ with $|A|=|B|=|C|=n$, we can compute the set $S_{A,B,C} = \{ab+c \mid a \in A, b \in B, c \in C\}$. I am interested in the minimum sized $S_{A,B,C}$ when ...
10
votes
0answers
154 views

Generalizing the growth of sums of two squares

Consider the set $S$ of numbers which are the sum of two (integer) squares, and define $S(n)$ as the number of members of $S$ in $\{1,2,\ldots,n\}.$ It is well-known that $$ S(n) \sim \frac{Kn}{\sqrt{\...
10
votes
0answers
222 views

Bear of an integral

I have a pretty ferocious integral to solve, and would be over the moon if I were able to get some sort of analytic expression / insight for it. $$ I = \int_{r}^{\infty} r_0^{-5/2} W_{-i\alpha'/2, \...
10
votes
0answers
800 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 present....
10
votes
0answers
563 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 ...
9
votes
0answers
116 views

Asymptotic value of card drawing game

A deck consisting of $r_0$ red cards and $b_0$ black cards is randomly shuffled. The host turns up the cards one at a time; if it is red, you get $\$1$; otherwise you pay the host $\$1$ (and you're ...
9
votes
0answers
897 views

Asymptotic large order approximation for Bessel function expression

How does one find the asymptotic large order approximation for $\sup_{0\le x\le\infty} \left(\sqrt{x} J_n(x)\right)$, where $J_n$ is the Bessel function of the first kind and order $n$. This is NOT a ...
9
votes
0answers
177 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 $r_n(...
8
votes
0answers
1k views

Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims that ...
7
votes
0answers
152 views

Recurrence $a_{n}=a_{\lfloor 2n/3\rfloor}+a_{\lfloor n/3\rfloor}$

I am considering the sequence $$a_n=a_{\lfloor 2n/3\rfloor}+a_{\lfloor n/3\rfloor}$$ with $a_0=1$, and I would like to calculate the limit $$\lim_{n\to\infty} \frac{a_n}{n}$$ I have seen this famous ...
7
votes
0answers
176 views

Only three types of limit of distributions truncated to a finite interval in the upper tail?

Suppose random variable $X$ has a continuous probability distribution with an unbounded upper tail; that is, the CDF of $X$ (call it $F$) is absolutely continuous and $F(x)<1$ for all $x\in\mathbb{...
7
votes
1answer
186 views

Truncated taylor series inequality

I came across the following fact in a paper and am having trouble understanding why it is true: Consider the error made when truncating the expansion for $e^a$ at the $K$th term. By choosing $K = O(\...
7
votes
0answers
129 views

What is known about the counting function of Gaussian primes"

The counting function of primes among $\Bbb{N}$, describing the asymptotic density of the primes, is well known (the Prime Number theorem). Let's define a mild generalization of the counting function ...
7
votes
0answers
124 views

Counting the size of the largest sets of independent strings

This question derives from a PPCG coding challenge I posed previously. For a given positive integer $n$, consider all binary strings of length $2n-1$. For a given string $S$, let $L$ be an array of ...
7
votes
0answers
276 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
99 views

What is the expected value of this game for large N?

For a given even $N$, I have $N/2$ red cards and $N/2$ black cards. Each time I draw a black card I win a dollar, each time I draw a red card I lose a dollar. I can stop at any time I like (and ...
6
votes
1answer
369 views

A rough proof for infinitesimals?

I discovered the following relation for arbitrary $d_r$: $$ \lim_{k \to \infty} \lim_{n \to \infty}\ \sum_{r=1}^n d_r \left( f(\frac{k}{n}r)\frac{k}{n} \right) = \lim_{s \to 1} \! \underbrace{\...
6
votes
0answers
158 views

Does $N_0(T) =N(T)$ where $N$ is the exact Riemann $\zeta$ zero counting function and $N_0$ is the approximate zero counting function imply the RH?

From A theory for the zeros of Riemann ζ and other L-functions The main new result is that the zeros on the critical line are in one-to- one correspondence with the zeros of the cosine ...
6
votes
0answers
128 views

Estimation of the number of solutions for the equation $\sigma(\varphi(n))=\sigma(\operatorname{rad}(n))$

For integers $n\geq 1$ in this post we denote the square-free kernel as $$\operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p,$$ that is the product of distinct primes dividing an ...
6
votes
0answers
100 views

A naive conjecture about Taylor series convergence

Conjecture. Let $f$ be a real (or complex) analytic function defined on some open subset $U$ of real (complex) numbers and assume that $p,q,x\in U$ are such that $x\in B(p,r_p)\cap B(q, r_q)$, where $...
6
votes
0answers
181 views

Fractional part summation and asymptotic expansion error

Let us consider the sum $$\displaystyle T_K=\sum_{n \geq \sqrt{K}}^{{K}} \left\{ \sqrt {n^2-K} \right\} $$ where $K$ is a positive integer and where $\{ \}$ indicates the fractional part. Its ...
6
votes
0answers
239 views

$K$-functional between $\ell_1$ and $\ell_2$ for a specific sequence

Short version: For any $n\in\mathbb{N}$, Let $$ p_n(k) \stackrel{\rm def}{=} \frac{1}{(k+1)\ln(k+1)}, \qquad 1\leq k\leq n-1 $$ and consider $$ \kappa_{p_n}(t) = \inf\{ \lVert u\rVert_1+t\lVert v\...
6
votes
0answers
335 views

Useful reformulation of Goldbach's conjecture?

Let us assume there exists some infinite order differential equation whose solution is: $$ y= \sum_{n=1}^\infty A_n \exp(p_n^sx) $$ Where $p_n$ is the $n$'th prime. Substituting $ y=\exp(\lambda x)$...
6
votes
0answers
94 views

If the primes were different, how many numbers would there be?

Given a set $S=\{s_1,s_2,\ldots\}$ of pairwise coprime positive integers greater than 1, define $T$ as the set of products of zero or more elements of $S$ so $T$ contains $1, s_1, s_2, s_1^2, s_1s_2,$ ...
6
votes
0answers
161 views

On the change $u=x^{1+\frac{1}{p_n}}$ in $\log \zeta(s)=s\int_0^\infty\frac{\pi(x)}{x(x^s-1)}dx$, where $p_n$ is the nth prime number

In [1] Wikipedia say that for $\Re s>1$ the Riemann zeta function satisfies $$\log \zeta(s)=s\int_0^\infty\frac{\pi(x)}{x(x^s-1)}dx,$$ where $\pi(x)$ is the prime counting function, and say too ...
6
votes
0answers
196 views

From $\prod_{d\mid n}d=n^{\sigma_0(n)/2}$ to $n!=\operatorname{lcm}(1,\ldots,n)^{e(n)}$, where $\sigma_0(n)$ is the number of divisors

We know that $$\prod_{d\mid n}d=n^{\sigma_{0}(n)/2}$$ for every integer $n\geq 1$, where $\sigma_{0}(n)$ is the number of positive divisors of $n$, see for example [1] (exercise 10, page 47). And for ...
6
votes
1answer
211 views

The asymptotic of the number of integers that are sums of three nonnegative cubes

Let $c(n) $ be the number of distinct integers between $0 $ and $n $ of the form $ a^3 + b^3 + c^3$, meaning the sum of $3$ nonnegative cubes. $C(n) = O( n \space \ln(n)^x ) $ Find and prove the ...
6
votes
0answers
71 views

Comparing asymptotic forms of series

I've run into some asymptotic analysis in research here and there and largely it feels pretty magical to me. My research has led me to consider the following question which I haven't the slightest ...
6
votes
0answers
4k 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
189 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: $$T(...
6
votes
0answers
276 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 ...
6
votes
0answers
388 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 ...
6
votes
0answers
229 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: $$\frac{1}{x}\left(\sum_{k=1}^xM(k)...
6
votes
0answers
144 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
1answer
84 views

Asymptotic behaviour of sum of decreasing definite integrals

I would like to calculate: \begin{equation*}g(K, T) = \displaystyle \sum_{k=1}^{K} \sum_{t = 1}^{T} \int_{0}^{1} \left(1 - z^k\right)^t \, dz. \end{equation*} If no closed form solution exists, I ...
6
votes
0answers
316 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), ...
6
votes
0answers
261 views

Weighted sum of ratio of partial sum of binomial coefficients

I would like to approximate the following sum when $n \rightarrow \infty$ and $n \gg k$, $$\sum_{x = k}^n \sum_{y > x}^n \frac{\sum_{m = 0}^{k - 1} {y - 2 \choose m}}{\sum_{m = 0}^k {y - 1 \choose ...