The lower-bounds tag has no usage guidance.

**0**

votes

**0**answers

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

**4**

votes

**0**answers

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

**0**

votes

**1**answer

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

**7**

votes

**2**answers

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

**1**

vote

**1**answer

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

**3**

votes

**1**answer

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

**0**

votes

**0**answers

32 views

### Deriving inequalities from a polynomially-bounded derivative

In this paper (p. 2, definition/remark) the following notion of ‘polynomial growth’ is defined for a non-negative real function $g(x)$ and a real constant $b\in(0;1)$:
There exist positive ...

**1**

vote

**1**answer

45 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: ...

**4**

votes

**1**answer

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

**2**

votes

**0**answers

98 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

**1**answer

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

**1**

vote

**2**answers

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

**3**

votes

**1**answer

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

**8**

votes

**1**answer

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

**0**

votes

**0**answers

103 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} = ...

**0**

votes

**0**answers

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

**0**

votes

**0**answers

73 views

### Looking for tighter bounds

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

**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},\ ...

**3**

votes

**2**answers

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

**3**

votes

**2**answers

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

**2**

votes

**2**answers

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

**0**

votes

**1**answer

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

**5**

votes

**1**answer

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

**2**

votes

**0**answers

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

**8**

votes

**0**answers

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

**1**

vote

**0**answers

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

**6**

votes

**2**answers

393 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)?
...

**2**

votes

**2**answers

337 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

**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

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

**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

**2**answers

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

**4**

votes

**1**answer

636 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? ...

**1**

vote

**1**answer

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

**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)$ ...

**2**

votes

**2**answers

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

**5**

votes

**1**answer

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

**8**

votes

**0**answers

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

**15**

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