The lower-bounds tag has no usage guidance.

**17**

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_{...

**16**

votes

**4**answers

2k 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 ...

**14**

votes

**6**answers

4k 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)$ ...

**8**

votes

**1**answer

319 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 ...

**8**

votes

**2**answers

402 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 (...

**8**

votes

**0**answers

370 views

### Bounding the probability that a random variable is maximal

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 for ...

**8**

votes

**0**answers

606 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 ...

**6**

votes

**2**answers

423 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 ...

**5**

votes

**1**answer

139 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 ...

**5**

votes

**1**answer

461 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!)$, ...

**5**

votes

**1**answer

248 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?

**4**

votes

**3**answers

2k 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 ...

**4**

votes

**1**answer

667 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? (...

**4**

votes

**1**answer

235 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 &...

**4**

votes

**2**answers

1k 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?

**3**

votes

**1**answer

438 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.

**3**

votes

**2**answers

758 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 ...

**3**

votes

**2**answers

164 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
$$\...

**3**

votes

**2**answers

154 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}^...

**3**

votes

**2**answers

1k 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{\...

**3**

votes

**2**answers

145 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 ...

**3**

votes

**1**answer

216 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 ...

**3**

votes

**0**answers

131 views

### A generalization of coupon collector problem - $\geq1$ pick per experiment

Mix $T\geq1$ coupons numbered $1$ to $T$ with a set of $S\geq0$ number of dummy coupons with no numbers. Select $N\geq1$ coupons at each trial at random and put them back.
$N=1$ is standard coupon ...

**2**

votes

**2**answers

350 views

### lower bound for $\Re\zeta(1+it)$

Hi
is there any lower bound for $\Re\zeta(1+it)$.
I did try with computer until some ordinate and I saw $\Re\zeta(1+it)>0$.
If it is true, is there any reference to prove it.
thanks

**2**

votes

**1**answer

123 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(...

**2**

votes

**2**answers

348 views

### Lower bounds on derivative around zero set of a positive smooth function

As part of a different problem, I came across the following simplified question, for which I cannot exhibit a proof nor a counterexample. Note that the assumptions of smoothness and strict positivity ...

**2**

votes

**0**answers

58 views

### Minimal condition $\sum \rho_{ij} \Psi_{ij} s_i s_j < \sum s_i s_j $, $\mid \rho_{ij} \mid \leq 1$, $s_i \in \mathbb R$ and $\Psi_{ij} \in \{0,1\}$

Consider a sequence of real number $\{s_i\}_{i\leq n}$. Now consider the real numbers $F$, $G$ and $\alpha$ defined below
$$F= \sqrt{ \left( \sum ~\rho_{ij} ~\Psi_{ij}~ s_i ~s_j \right)^+}, $$
$$G = ...

**2**

votes

**1**answer

133 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=\...

**2**

votes

**0**answers

137 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 ...

**2**

votes

**0**answers

103 views

### Lower asymptotic bounds for the derivative of Laguerre polynomials

Let $ L_{d}^{(1)}(x)$ denote the generalized Laguerre polynomial of degree $d$ and order $\alpha=1$. Clearly, since all the roots $r_1,\dots,r_d$ of $L_{d}^{(1)}$ are simple, there exists a strictly ...

**1**

vote

**3**answers

164 views

### Minimum number of unlabeled planar graphs

Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$?
Alternatively, a lower bound on the number of all ...

**1**

vote

**1**answer

117 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 ...

**1**

vote

**1**answer

66 views

### Bound on the weight of the minimum weight generator of [n,k] cyclic codes?

I'm looking at creating sparse generator matrices for cyclic codes of a given length and dimension. A generator matrix of an [n,k] cyclic code can be expressed as
$G = \begin{bmatrix}g_0 & g_1 &...

**1**

vote

**1**answer

56 views

### Expectation of logarithmic of a Laplace random varible

Say $Y$ is a random variable with Laplace distribution with zero mean and variance parameter $b$. I am trying to compute the expectation of $\ln(Y+\alpha)$ ($\alpha>0$), that is: $$\int^{\infty}_{0}...

**1**

vote

**1**answer

355 views

### Lower bound on the convergence rate of a specific Markov chain

I have a Markov chain $\mathbf{A} = (A_0, A_1, \ldots)$ with state space $\{0, \ldots, n\}$ which converges towards a stationary distribution $\pi$. There are a lot of well-known results on upper-...

**1**

vote

**0**answers

59 views

### Finding the infimum of the range of a certain non-negative function associated to a $ C^{*} $-algebra

Let $ A $ be a non-trivial $ C^{*} $-algebra and $ n \in \mathbb{N} $. Setting $ \mathcal{D} \stackrel{\text{df}}{=} A^{n} \setminus \{ (0_{A},\ldots,0_{A}) \} $, we can define a function $ f: \...

**1**

vote

**0**answers

45 views

### Bounds on $\sum_{j=1}^m\frac{\pi^j}{\Gamma(j)(x^2+(j+1/4)^2)}$

During our search of real rooted entire function approximations to Riemann $\Xi$ function, we need to calculate the upper and lower bounds of
$$f_m(x):=\sum_{j=1}^m b_j(x):=\sum_{j=1}^m\frac{\pi^j}{\...

**1**

vote

**0**answers

122 views

### Bounding the Schur's complement of similiar matrices

Assume the following:
• $L\leq K$
.
• $\Gamma\in M_{K,L}$ is a $L$ rank ${ 0,1} $ matrix, without identical rows or the zeros row.
• $N\in M_{K,K}$ is a diagonal matrix, whose diagonal is a ...

**1**

vote

**0**answers

94 views

### Bounding a q-expansion on a bounded open subset of the complex upper-half plane

Let $f:\mathbf{H}\to \mathbf{C}$ be a holomorphic function on the complex upper-half plane and let $q:\tau\mapsto \exp(\pi i \tau)$ be the nome on $\mathbf{H}$. Suppose that there are integers $a_j$ ...

**1**

vote

**0**answers

228 views

### Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from
http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)
The following ...

**0**

votes

**1**answer

261 views

### Good lower bound on matching in bipartite graph

Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not ...

**0**

votes

**0**answers

40 views

### When does the equality hold in Dias da Silva - Hamidoune Theorem?

Let $p$ be prime number and let $A$ be a $k$-elements subset of $\mathbb{Z}/p\mathbb{Z}$. Dias da Silva - Hamidoune Theorem states that $|h^{\hat{}}A| \geq \min(p, hk -h^2 + 1)$, where $h$ is an ...

**0**

votes

**0**answers

110 views

### Eigenvalue bounds from eigenvalues of Schur complement

Is it possible to lower bound the minimal eigenvalue of a symmetric PSD matrix
$M= \begin{pmatrix}A & C\\ C^*&B\end{pmatrix}$
from the knowledge of the eigenvalues of $M$'s Schur complement ...

**0**

votes

**0**answers

110 views

### Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = 1,f_{...

**0**

votes

**0**answers

119 views

### partition of an integer n into atmost k =O(log n) parts

Suppose you have a partition p of n into atmost k parts, say $$\{i_1, i_2, ..., i_j, ..., i_{k-1}\}$$
For example $\{1, 4\}$ is a partition of 10 into 3 parts (in this notation i am specifying the ...