Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
137 questions
3
votes
2
answers
283
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}^...
- 618
3
votes
0
answers
268
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 ...
user76479
3
votes
1
answer
212
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=\...
- 91
11
votes
2
answers
1k
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 (...
- 3,223
1
vote
1
answer
143
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 &...
- 111
4
votes
1
answer
749
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 ...
- 2,221
1
vote
1
answer
81
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}...
- 11
4
votes
1
answer
441
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,661
3
votes
1
answer
575
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 ...
- 217
3
votes
1
answer
679
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(...
- 195
1
vote
3
answers
238
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 ...
- 11
3
votes
1
answer
860
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.
- 1,890
8
votes
1
answer
605
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 ...
- 841
0
votes
0
answers
131
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_{...
- 3,463
0
votes
0
answers
212
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 ...
- 1
3
votes
1
answer
199
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,440
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_{...
- 11.4k
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{\...
- 285
3
votes
2
answers
190
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 ...
- 13.9k
2
votes
2
answers
518
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 ...
- 83
0
votes
1
answer
726
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 ...
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!)$, ...
- 2,350
2
votes
0
answers
137
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 ...
- 959
11
votes
0
answers
536
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 ...
- 119
1
vote
0
answers
148
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 ...
- 295
6
votes
2
answers
743
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 ...
- 577
1
vote
0
answers
109
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$ ...
- 11
3
votes
0
answers
299
views
Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric
Slight extension of cross posting from
https://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there)
The ...
- 800
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?
- 111
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 ...
- 5,974
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? (...
1
vote
1
answer
648
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-...
- 113
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)$ ...
- 1,791
5
votes
3
answers
4k
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 ...
- 23k
5
votes
1
answer
271
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?
- 201
12
votes
0
answers
815
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 ...
- 121
24
votes
4
answers
5k
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 ...
- 2,416