# Questions tagged [lower-bounds]

The lower-bounds tag has no usage guidance.

79
questions

**0**

votes

**0**answers

172 views

### is it possible to prove this :$\sum_{n\le X}\tan(n!)=\mathcal{O}(X^{\alpha})$?, $\alpha <1$?

This series $\sum_{n\geq 0}\tan(n!)$ probably diverges. I want to find a polynomial bounding $|\sum_{n\le X}\tan(n!)|$. Is it possible to prove that $\sum_{n\le X}\tan(n!)=\mathcal{O}(X^{\alpha})$ ...

**7**

votes

**0**answers

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

**0**

votes

**1**answer

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

**-1**

votes

**1**answer

146 views

### Any simplification of this inequality if it is true? :For $t\geq 1.22$: $|\zeta(0.5+it)|\leq 0.5 \frac{|\Gamma(0.5+it)|}{|\Gamma(-0.5+it)|}$

When I tried to give bounds for $\zeta(0.5+it)$ using some transformations over Gamma function using the function $f(x)=\exp(-n x)$ over the range $(0,+\infty)$ , For $ Re(s)=\frac12 $ and $t >0$ ...

**0**

votes

**0**answers

48 views

### if $\max_{z \in K} |\zeta(z+it)-f(z)|<\epsilon.$ then is this $\lim_{t\to \infty} \inf \frac {|\zeta'(z+it)|}{|f'(z)|} $ a finit limit?

Universality theorem of Riemann zeta function states that :Let $K$ be a compact subset with connected complement lying in the strip $\{1/2 < \operatorname{Re}(z)<1\}$, and let $f : K \rightarrow ...

**3**

votes

**2**answers

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

**0**

votes

**1**answer

129 views

### Survey papers on spectral radius [closed]

Let $M$ be a $n\times n$ matrix.
Are there any survey papers which give lower and upper bounds on its spectral radius?
What are the ways to find some lower bounds and upper bounds on $\rho(M)$ ...

**2**

votes

**1**answer

107 views

### Lower-bound for $E[\min(X, k)]$ where $X$ is sum of Bernoulli random variables with $E[X]$ being a linear function of $k$

Given a real number $\alpha \in [0.5, 1.5]$, an integer number $k>1$, and a set of independent Bernoulli random variables $x_1, \dots, x_n$, I am interested to find a lower-bound for $F(\alpha, k)= ...

**0**

votes

**1**answer

82 views

### Are there known bounds on the expectation of the truncated Beta distribution?

Let $X\sim beta(\alpha,\beta)$ be a random variable and let $\tau\in(0,1)$.
Are there any known closed-form bounds (I'm specifically interested in lower bounds) on
$$
\mathbb E[X\ | X\le \tau]?
$$

**2**

votes

**1**answer

111 views

### Minimum local permutation data needed to globally merge locally sorted sequences?

We have $k$ blocks of integer sequences $B_1,\dots,B_k$ where $B_i$ is a sequence $$a_{i,1},\dots,a_{i,n_i}$$ with $a_{i,j}\leq a_{i,j+1}$.
Denote the permutation matrix $M_{\ell,\ell'}$ that merges $...

**3**

votes

**2**answers

197 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)\:=\:\...

**5**

votes

**3**answers

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

**1**

vote

**0**answers

103 views

### Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]

The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...

**0**

votes

**0**answers

125 views

### What do square roots as minimums have to do with Harmonic numbers?

In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series:
$$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...

**3**

votes

**2**answers

366 views

### Good upper bound for a certain sum

Given $\gamma \in [0, 1)$, an integer $N \ge 2$, and a decreasing null sequence of positive numbers $e_1,e_2,\ldots,e_t,\ldots$, I'm interested in estimating the sum $S_N := \sum_{t=1}^N\gamma^t e_{N-...

**1**

vote

**0**answers

66 views

### Bounds on spectral radius using chromatic number

I am struggling with this question:
If I have a connected graph $G$ on $n$ vertices and $m$ edges with chromatic number $d$ then how can I give a bound(lower and upper) on its spectral radius in ...

**2**

votes

**1**answer

228 views

### Complicated bound after using Stirling's approximation

I have this inequality $$\frac{1}{a}\exp\bigl\{-\frac{4}{h^2}\bigr\} \geq \frac{1}{f}$$ where $$ a \leq \Bigl(\pi^{d/2}\Gamma(\frac{1}{2}d+1)^{-1} + 1\Bigr) \left(\frac{h^{d+1}}{2} \Gamma \left(\frac{...

**3**

votes

**1**answer

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

**2**

votes

**1**answer

494 views

### Counting / characterizing the isolated points of a particular algebraic variety

I'm not a professional geometer / topologist, so please thanks for your patience :)
Setup
The following questions are the first in a series of steps I'm undertaking in an attempt to break down a ...

**1**

vote

**1**answer

444 views

### Any inequalities / estimates for a lower bound of the $L^2$ inner product of a quantity and its derivative?

For some numerical analysis of a fluid, I am wondering if there is any inequality that provides a lower bound (in the $L^2$ norm), for the $L^2$ inner product of a quantity with its derivative. In ...

**3**

votes

**1**answer

313 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):= \...

**3**

votes

**1**answer

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

**1**

vote

**1**answer

86 views

### A distribution which is Wasserstein-close to a compactly supported distribution is almost compactly supported

I wonder whether this is true: If a distribution is very close (in the Wassertein sense) to another distribution with compact support, then the former must put only tiny amount of mass outside a ...

**1**

vote

**2**answers

230 views

### Lower bound on misclassification rate of Lipschitz functions in terms of Lipschitz constant

Important note
@MateuszKwaśnicki in the comment section has raised a fundamental issue with the current statement of the problem. I'm trying to bugfix it.
Setup
I wish to show that a Lipschitz ...

**2**

votes

**1**answer

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

**6**

votes

**2**answers

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

**1**

vote

**0**answers

82 views

### Bounding quantiles of the noncentral chi distribution

I need to bound the empirical quantiles for a noncentral chi distribution (not chi-squared) $\chi_\nu(\lambda)$, where $\nu$ is the number of degrees of freedom and $\lambda$ the non-centrality ...

**0**

votes

**0**answers

95 views

### Lower bound for the probability that $X=\omega\left(\mathbb E[X]\right)$ for $X\sim Bin(n,p)$

Let $X\sim Bin(n,p)$ be a binomial variable and let $\delta\in (0,1)$.
I'm looking for a lower bound of the form $\Pr[X > f(\delta)] \ge \delta$.
Specifically, if $\delta,p=o(1)$ are not ...

**3**

votes

**2**answers

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

**2**

votes

**2**answers

75 views

### Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

In one dimension d=1 an equally-spaced set of N points in [0,1) has the lowest possible (star) discrepancy D=0.5/N. Unfortunately, I found only asymptotic bounds for other dimensions (e.g. acc. to ...

**5**

votes

**0**answers

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

**3**

votes

**0**answers

153 views

### Lower bound on number of $r$-regular graphs witn $n$ vertices

Consider the set of $r$-regular labeled graphs with $n$ vertices. There are results on its asymptotic size (see for instance this question on MO).
Is there a known, explicit lower bound on that size, ...

**1**

vote

**0**answers

53 views

### Cramer Rao bound for relative estimation

I have an observed vector ${\bf y}$ from which I would like to estimate a parameter vector ${\bf c}$ (denote the estimate $\hat{{\bf c}}$).
A feature of our estimation problem is that the involved ...

**4**

votes

**1**answer

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

**1**

vote

**0**answers

259 views

### Bound on eigenvalues of A+B (Hermitan matrices) which is better that the Lidskii and Weyl bounds

I have two positive definite $N\times N$ Hermitian matrices $A$ and $A$ and am interested in bounding the eigenvalues of $A+B$ in terms of the eigenvalues of $A$ and $B$. Let $\lambda_k(\cdot)$ be ...

**0**

votes

**2**answers

644 views

### Bounds on the smallest real positive root of a polynomial

I'm trying to find upper and lower bounds of the smallest positive root of a polynomial, stated in terms of its coefficients. As I appreciate it might be a very general problem, My specific interest ...

**2**

votes

**1**answer

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

**1**

vote

**0**answers

101 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: \...

**4**

votes

**2**answers

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

**7**

votes

**1**answer

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

**1**

vote

**0**answers

50 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}{\...

**2**

votes

**0**answers

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

**3**

votes

**2**answers

185 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

**0**answers

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

**3**

votes

**1**answer

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

**11**

votes

**2**answers

721 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

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

**4**

votes

**1**answer

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

**1**

vote

**1**answer

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

**4**

votes

**1**answer

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