# Questions tagged [lower-bounds]

The tag has no usage guidance.

114 questions
Filter by
Sorted by
Tagged with
1 vote
259 views

175 views

### An inequality involving binomial coefficients and the powers of two

I came across the following inequality, which should hold for any integer $k\geq 1$: $$\sum_{j=0}^{k-1}\frac{(-1)^{j}2^{k-1-j}\binom{k}{j}(k-j)}{2k+1-j}\leq \frac{1}{3}.$$ I have been struggling with ...
37 views

1 vote
103 views

### "Tails" of a multinomial distribution

Let $X_1,\dots,X_N$ denote a collection of independent samples of a uniform multinomial random variable in $\mathbb{Z}^k$, with the number of trials equal to $n\ll k$. (By "uniform", I mean ...
1 vote
29 views

### Are there known bounds on these ratios of chromatic polynomials?

The chromatic polynomial $P(G, \lambda)$ gives the number of proper vertex colorings of the graph $G$ with $\lambda$ colors. I'm interested in how many possible colorings you loose when you add an ...
76 views

### Gershgorin-type bounds for smallest eigenvalue of positive-definite matrix

I would like to know if there are known results for bounding eigenvalues of positive-definite matrices, in particular gram matrices $AA^\top$ based on easily computable functions of $A$. Gershgorin ...
105 views

### Size of an “average” ϵ-net on the unit sphere

This is a question I originally asked on math.stackexchange, but didn't receive a satisfying answer. Let $\epsilon>0$ and consider constructing a set $S_\epsilon\subseteq S^{d-1}$ of points on the ...
116 views

### Lower-bound smallest eigenvalue of covariance matrix of $y = f(Ax)$, for $x$ uniform on unit-sphere

Let $A=(a_1,\ldots,a_)$ be a fixed $k \times d$ matrix (with $d$ large), and $x$ be a random vector uniformly distributed on the unit-sphere in $\mathbb R^d$. Let $f:\mathbb R \to \mathbb R$ be a ...
1 vote
42 views

### Analytic lower-bound for minimal value of $\|x\|^2$ such that $\|Cx-b\|^2 \le c^2$ (a hyperellipsoid)

Let $C$ be an $n \times p$ matrix and $b$ be a column vector of length $n$, and $c>0$. Let $E := \{x \in \mathbb R^p \mid \|Cx-b\| \le c\}$, a hyperellipsoid in nonstandard position. Question 1. ...
1k views

### What is the limit of $a (n + 1) / a (n)$?

Let $a(n) = f(n,n)$ where $f(m,n) = 1$ if $m < 2$ or $n < 2$ and $f(m,n) = f(m-1,n-1) + f(m-1,n-2) + 2 f(m-2,n-1)$ otherwise. What is the limit of $a(n + 1) / a (n)$? $(2.71...)$
1 vote
25 views

### Given a unit vector $x\in\mathbb R^d$, what is the worst possible within-cluster sum of squares for 2-means clustering?

This is a question I originally posted to math.stackexchange.com but it didn't attract any answers, and I was wondering if someone here can help. Consider a unit vector $x\in\mathbb R^d$ ($\|x\|_2=1$)...
133 views

### Distance of low-rank matrices to the identity for the $\infty$-norm

I am trying to get a lower bound (or even the exact value) of $$\min_{X \in \mathbb{R}^{n\times n}} \|X - I_n\|_{\infty} \enspace \text{s.t.} \enspace \mbox{Rank}(X) = m$$ where $m \leq n$, and the ...
107 views

212 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 ...
176 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)$ ...
271 views

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 137 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 128 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} &...
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 ...