Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
24 votes
4 answers
4k views

Super-linear time complexity lower bounds for any natural problem in NP?

Do we know any problem in NP which has a super-linear time complexity lower bound? Ideally, we would like to show that 3SAT has super-polynomial lower bounds, but I guess we're far away from that. I'd ...
Rune's user avatar
  • 2,386
20 votes
1 answer
1k views

Quantitative lower bounds related to Zhang's theorem on bounded gaps

Let $\mathcal{H}=\left\{ h_{i}\right\} _{i=1}^{k}$ be an admissible set, and define $$\pi_{\mathcal{H}}(x)=\left|\left\{ n\leq x\ :\ \exists\ i,j\leq k,\ i\neq j\ \text{such that both }n+h_{i},\ n+h_{...
Eric Naslund's user avatar
  • 11.3k
17 votes
6 answers
10k views

Lower bounds for chromatic number of a graph

I am trying to find a good lower bound for chromatic number of one family of graphs. I'm curious what are the known lower bounds for chromatic number. There are two obvious: $\chi(G) \geq \omega(G)$ ...
ilyaraz's user avatar
  • 1,771
12 votes
0 answers
799 views

Lower bounds for linear forms of logarithms (a la Baker)?

Let $\lambda_1$, $\lambda_2$, and $a$ be three fixed complex algebraic numbers. For a given integer $n$, write $\Theta(n) = \arg(a \lambda_1^n + \lambda_2^n)$. Assuming $\Theta(n)$ is not zero, I am ...
Joel Ouaknine's user avatar
11 votes
3 answers
1k views

What is the limit of $a (n + 1) / a (n)$?

Let $a(n) = f(n,n)$ where $f(m,n) = 1$ if $m < 2 $ or $ n < 2$ and $f(m,n) = f(m-1,n-1) + f(m-1,n-2) + 2 f(m-2,n-1)$ otherwise. What is the limit of $a(n + 1) / a (n)$? $(2.71...)$
José María Grau Ribas's user avatar
11 votes
2 answers
986 views

Lower bound on the first eigenvalue of the Laplace-Beltrami on a closed Riemannian manifold

It has been proved by Li-Yau and Zhong-Yang that if $M$ is a closed Riemannian manifold of dimension $n$ with nonnegative Ricci curvature, then the first nonzero eigenvalue $\lambda_1(M)$ of the (...
Raziel's user avatar
  • 3,153
11 votes
0 answers
524 views

Bounding the probability that a random variable is maximal

Question: Suppose we have $N$ independent random variables $X_1$, $\ldots$, $X_N$ with finite means $\mu_1 \leq \ldots \leq \mu_N$ and variances $\sigma_1^2$, $\ldots$, $\sigma_N^2$. I am looking ...
MLS's user avatar
  • 119
9 votes
1 answer
635 views

The expected value of product of random variables which have the same distribution but are not independent

Given a positive integer $k$, is there a positive real number $c(k)$ such that $\mathbb{E}\left(\prod_{i=1}^k X_i\right)\geq c(k)$ for any $k$-random variables $X_1,X_2,\ldots,X_k$ which all have the ...
fengzju's user avatar
  • 99
8 votes
2 answers
913 views

Lower bound on exponential sums

Let $k\geq 2$. Consider the following norm of exponenetial sum: $$ I(N,p,k)=\int_0^1\int_0^1 \left|\sum_{n=0}^N e^{2\pi i (n x+n^k y)}\right|^p dxdy. $$ Bourgain mentioned on Page 118 of https://...
Thomas Yang's user avatar
8 votes
1 answer
581 views

lower and upper bound for $\sum_{k=1}^n \frac{(-1)^{\Omega(k)}}k$?

Are there known any lower and upper bounds for $$ \sum_{k=1}^n \frac{(-1)^{\Omega(k)}}k, $$ where $\Omega(n)$ is the number of prime factors counting multiplicities of $n$? Or at least is it known ...
asad's user avatar
  • 841
8 votes
2 answers
704 views

Lower bound on the entries of the Perron vector

Let $A$ be a matrix that satisfies all the conditions of Perron- Frobenius theorem. From the theorem it is known that the entries of the eigenvector corresponding to the largest eigenvalue will be ...
biryani's user avatar
  • 183
8 votes
0 answers
265 views

Restricted divisor summatory function

I have a problem that boils down to prove that the succession $\{a_n\}$ tends to infinity, where $$a_n:=1+\sum_{0\leq j<n}D_{2j+1}(n-j)$$ and $D_{m}(n)$ is the number of divisors $d>1$ of $n$ ...
Nick Belane's user avatar
7 votes
1 answer
326 views

lower bound for Perron-Frobenius degree of a Perron number

A Perron number is an algebraic number which is greater than one in absolute value and is greater than all of its Galois conjugates in absolute value as well. Lind's theorem states that any Perron ...
Mehdi Yazdi's user avatar
7 votes
2 answers
3k views

Lower bound for Euler's totient for almost all integers

Let $\varphi(n)$ be the Euler's totient function. It is well know that $\liminf_{n \to \infty} \frac{\varphi(n)}{n / \log \log n} = e^{-\gamma}$, so that for $\varepsilon > 0$ it results $\frac{\...
user21706's user avatar
  • 255
7 votes
1 answer
282 views

Is this lower bound for the size of minimal vertex cover new/interesting?

I have found this lower bound for the size of minimal vertex cover (and proved it). If a simple connected graph G on n vertices has largest and smallest eigenvalues $\lambda_1,\lambda_n$, ...
Yahav Boneh's user avatar
6 votes
2 answers
722 views

bound for zeros of a polynomial with bounded integer coefficients

Let $f$ be a monic polynomial with bounded integer coefficients and such that all zeros are (in absolute value) greater than $1$. How close can the zeros of $f$ reach $1$ (in absolute value)? More ...
Daniel Krenn's user avatar
6 votes
2 answers
4k views

tight bounds on probability of sum of laplace random variables.

Are there tight upper and lower bounds on the density of the sum of $n$ i.i.d laplace random variables that depend on $n$ and the individual laplacian densities?
Vedarun's user avatar
  • 111
6 votes
1 answer
1k views

Simple lower bounds for Bell numbers (number of set partitions)?

The $n$-th Bell number $B_n$ represents the number of distinct partitions of a set with $n$ distinguished elements. It can be expressed as the infinite sum $B_n = (1/e)\sum_{k=1}^{\infty} (k^n/k!)$, ...
András Salamon's user avatar
5 votes
4 answers
817 views

Limit of a sum with binomial coefficients

Let $$A_k = \frac{\sum_{i=1}^ki{2k-i-1 \choose i-1}{i-1 \choose k-i}}{k{2k-1\choose k}}$$ $$B_k = \frac{\sum_{i=1}^ki{2k-i-2 \choose i-1}{i \choose k-i}}{k{2k-1\choose k}}$$ $$C_k = \frac{\sum_{i=1}^k(...
macat's user avatar
  • 145
5 votes
3 answers
3k views

Proofs of Lower Bounds for Ramsey Numbers?

As a sort of dual question to this question, I am wondering what proofs people know of lower bounds on Ramsey numbers $R(k, k)$. I know of two proofs: there is Erdos's beautiful probabilistic ...
Daniel Litt's user avatar
  • 22.2k
5 votes
2 answers
1k views

Nontrivial lower bound on the sum of matrix norms

Let $X, V\in\mathbb{R}^{n\times r}$ such that $X^\top V$ is symmetric. The central quantity I care about is \begin{equation} \|XV^\top\|_{F}^2+\|X^\top V\|_{F}^2 +[\text{Tr}(X^\top V)]^2. \end{...
Wuchen's user avatar
  • 505
5 votes
1 answer
1k views

Best lower bound for off-diagonal Ramsey numbers

What are the current best lower bounds for off-diagonal Ramsey numbers $R(k,l)$ with $l$ of order unity and asking for asymptotic behavior for large $k$, such as $R(k,4)$, $R(k,5)$, and so on? (...
matt hastings's user avatar
5 votes
2 answers
604 views

Lower Bounds for the Roots of Polynomials

I'm interested in the "size" of the roots of a sequence of Taylor Polynomials of an entire function. For example, consider $\mathrm f(z) = \mathrm e^z$. The Taylor Polynomials, or $k$-jets, are $$\...
Fly by Night's user avatar
5 votes
2 answers
208 views

Distance of low-rank matrices to the identity for the $\infty$-norm

I am trying to get a lower bound (or even the exact value) of $$ \min_{X \in \mathbb{R}^{n\times n}} \|X - I_n\|_{\infty} \enspace \text{s.t.} \enspace \mbox{Rank}(X) = m $$ where $m \leq n$, and the ...
PAb's user avatar
  • 187
5 votes
3 answers
143 views

Fast computation of a ball with radius r with largest number of input points

We are given a set S of n points equipped with some metric and an integer $r>0$. We define $B(x,r) \subseteq S$ (the ball with radius r centered in x) to be the set of points in S within distance r ...
Mauro Sox's user avatar
5 votes
1 answer
828 views

Hausdorff distance is a lower (or upper bound) for what probability metric?

In a metric space $X=(X, d)$, given a probability measure $\mu$ and two subsets $A$ and $B$ of positive measure, it's not hard to prove that $$ d(A, B) \le W(\mu|_A, \mu|_B), $$ where $d(A, B):= \...
dohmatob's user avatar
  • 6,716
5 votes
1 answer
270 views

Feasibility of linear programs

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
Vinayak Pathak's user avatar
5 votes
0 answers
84 views

Smaller root of a difference of products of polynomials with integer bounded coefficients

Is there a positive constant $K>0$ such that for every polynomials $f_1,\dots,f_4 \in\mathbb{Z}[X]$ with coefficients in {-1,0,1}, every positive root $x$ of the polynomial $$g=f_1f_2-f_3f_4$$ ...
A. Lampadophore's user avatar
4 votes
2 answers
1k views

Lower bound on the first eigenvalue of the Laplacian of a Riemann surface with constant negative scalar curvature

A friend in physics asked this question, and I didn't know the answer. Are there lower bounds on the first eigenvalue of the Laplacian of a Riemann surface equipped with a metric of constant negative ...
user1504's user avatar
  • 5,869
4 votes
2 answers
260 views

An inequality involving binomial coefficients and the powers of two

I came across the following inequality, which should hold for any integer $k\geq 1$: $$\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-j)}{2k+1-j}\leq \frac{1}{3}.$$ I have been struggling with ...
macat's user avatar
  • 145
4 votes
1 answer
225 views

Bounds for the crossing number in terms of the braid index?

Is there a lower bound on the crossing number of a knot (resp., link) with braid index $b$? For knots, I believe the smallest crossing number for braid index 2 is 3, the smallest crossing number for ...
Charles's user avatar
  • 8,974
4 votes
1 answer
157 views

Existence of copula bound pointwise strictly smaller than the Fréchet-Hoeffding upper bound

Consider bivariate copulas $C_1$ and $C_2$ with $\max\{C_1(u,v), C_2(u,v)\}< M_2(u,v)$ for all $u,v \in(0,1)$, where $M_2(u,v) := \min\{u,v\}$ is the Fréchet-Hoeffding upper bound. Is there a ...
Corram's user avatar
  • 143
4 votes
1 answer
713 views

Lower bound on the tail of the hypergeometric distribution

Suppose there is a bag with $M$ white marbles and $N - M$ black marbles. Let $H(n, N, M)$ be a random variable which is number of white marbles in a draw, without replacement, of $n$ marbles from a ...
Nate Ackerman's user avatar
4 votes
1 answer
409 views

A lower bound on the $L^2$ norm of a Dirichlet polynomial

The Question. Suppose $0 < \alpha < \beta$ are fixed, and $a_n$ is an arbitrary sequence of real numbers. Is it known how to bound from below \begin{equation*} \int_0^{T} \Big| \sum_{\alpha T &...
Matt Young's user avatar
  • 4,633
4 votes
1 answer
228 views

Expectation over Pareto Sums

Given $K$ iid random variables $x_i$ with uniform distribution on $(0,1]$ and a constant $\alpha > 0$, the random variable $x_i^{-\alpha/2}$ is Pareto-distributed with scale parameter $1$ and ...
August.xxz's user avatar
4 votes
0 answers
122 views

Log of a truncated binomial

Let $X$ follow a binomial distribution with $n$ trials and success probability $p$, and let $0\leq k\leq n$. Are there any natural approximations or bounds for the ratio $$\frac{\boldsymbol{E}\log\...
Tom Solberg's user avatar
  • 3,929
3 votes
1 answer
821 views

Lower bounds on the error term of the prime number theorem

Are there any lower bounds on the error term for the prime number theorem, or in other words, is there a nontrivial $f$ s.t. $$f(x)\ll |\psi(x) - x|$$ where $\psi$ is the Chebyshev function.
Mayank Pandey's user avatar
3 votes
3 answers
5k views

Probability of a random variable greater than its expected value

We have a lot of probabilities lower bounding as (e.g. chernoff bound, reverse markov inequality, Paley–Zygmund inequality) $$ P( X-E(X) > a) \geq c, a > 0 \quad and \quad P(X > (1-\theta)E[...
exteral's user avatar
  • 141
3 votes
2 answers
249 views

Given a polynomial constraint equation in $n$ variables, can one conclude that the sum of the variables is non-negative?

Currently I'm stuck as follows; at least a positive proof if $n=3$ would be a great nice-to-have! Consider real numbers $x_1,x_2,\dots,x_n$ satisfying $$\prod^n_{k=1}\left(1-x_k^2\right)\:=\:\...
Hanno's user avatar
  • 489
3 votes
1 answer
86 views

If $X \sim N(0,I_m)$, what is a necessary and sufficient condition on $u_m > 0$ such that $\lim\sup_{m\to \infty} P(\|X\|^2 \ge u_m|X_1|) = 1$

Let $m$ be a large positive integer and $X=(X_1,\ldots,X_m) \sim N(0,I_m)$. I wish to show that the squared norm of $X$ is much much bigger than the absolute value of any of the $X_j$'s. For example, ...
dohmatob's user avatar
  • 6,716
3 votes
2 answers
261 views

Lower bound for Euler's function

Euler function is defined, for $|x|\le 1$, as follows: $$\phi(x)=\prod_{i=1}^\infty(1-x^i)$$ Upper bounds for $\phi$ can be simply derived from ending the product early, e.g. $$\phi(x)<\prod_{i=1}^...
R B's user avatar
  • 608
3 votes
2 answers
228 views

Lower bounding decoding error in a noisy adversarial channel

Problem description Suppose we have a finite alphabet $\mathcal{X}$, where each letter $X \in \mathcal{X}$ indexes into some fixed set of distributions, $\{P_{1},\ldots,P_{|\mathcal{X}|}\}$. For ...
user124784's user avatar
3 votes
1 answer
159 views

Lower bound on the sum of pmf squared of a hypergeometric distribution

I am working on a proof of correctness for an algorithm I came up with. I encountered the following problem en route. I would appreciate if anyone had some idea or could point me to the relevant ...
User93's user avatar
  • 33
3 votes
2 answers
816 views

Large deviation upper bound for Chi-squared random variable

Let $X \sim \chi^2_n$ random variable. I am looking for a large deviation upper bound for $X$. The answer here, says that Since you said that you're looking for an upper bound, it should also be ...
Greenparker's user avatar
3 votes
1 answer
196 views

Looking for tighter bounds on a certain solution of a nonlinear equation

I have to solve an equation which is $$\sum_{i=1}^N x_i = \sum_{i=1}^N y_i,$$ where $$x_i = \frac{z_i}{1 + (K_i - 1) w}$$ and $$y_i = \frac{K_i z_i}{1 + (K_i - 1) w}.$$ The $z_i$ are all positive ...
Claude Leibovici's user avatar
3 votes
1 answer
521 views

Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph? One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
Untitled's user avatar
  • 217
3 votes
1 answer
538 views

using polynomials as lower / upper bound?

I'm interested in the question of given a differentiable and bounded function $f(\vec{x})$ (over a single variable or multiple variables, over a bounded domain $D$), finding a pair of polynomials $p_1(...
Evan Pu's user avatar
  • 195
3 votes
2 answers
187 views

Techniques for showing optimality of given packing

There are some natural packing problems that have been asked in mathematics. Some of them are: 1)How many balls can be placed with in a cube? 2)How many equidistant points can be place on the ...
Turbo's user avatar
  • 13.7k
3 votes
1 answer
158 views

Non-asymptotic tail bounds for $D_{\text{Hellinger}}(P\|\hat{P}_N)$

Let P be a distribution on a finite set of size $k$ and let $\hat{P}_N=(N_1/N,\ldots,N_k/N)$ be the empirical distribution (frequencies) from a samples of size $N$. Consider the Hellinger distance ...
dohmatob's user avatar
  • 6,716
3 votes
1 answer
209 views

Possible lower bound in quantum many body system with non-local terms

I am asking a question related to Lieb-Robinson bound and nonlocality. As we know from Lieb-Robinson theorem (see e.g. http://arxiv.org/abs/1008.5137): Suppose a Hamiltonian system is local, i.e. $H=\...
Del Don's user avatar
  • 91