Questions tagged [lower-bounds]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
3answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
1answer
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
2answers
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
0answers
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
0answers
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
2answers
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
2answers
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
0answers
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
0answers
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
0answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
2answers
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
1answer
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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 &...