Questions tagged [lower-bounds]
The lower-bounds tag has no usage guidance.
51
questions with no upvoted or accepted answers
12
votes
0
answers
801
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
11
votes
0
answers
524
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
8
votes
0
answers
265
views
Restricted divisor summatory function
I have a problem that boils down to prove that the succession $\{a_n\}$ tends to infinity, where
$$a_n:=1+\sum_{0\leq j<n}D_{2j+1}(n-j)$$
and $D_{m}(n)$ is the number of divisors $d>1$ of $n$ ...
- 177
5
votes
0
answers
84
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$$
...
4
votes
0
answers
123
views
Log of a truncated binomial
Let $X$ follow a binomial distribution with $n$ trials and success probability $p$, and let $0\leq k\leq n$. Are there any natural approximations or bounds for the ratio $$\frac{\boldsymbol{E}\log\...
- 3,929
3
votes
0
answers
64
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
- 479
3
votes
0
answers
90
views
Probability of winning a $k$-rounds coin toss game
Let $p,q \in [0,1]$ with $p>q$. I denote by $B_k(p), B_k(q)$ two independent random variables following the binomial distribution, with parameters $(k,p)$ and $(k,q)$ respectively.
Informal ...
- 131
3
votes
0
answers
666
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 ...
- 6,726
3
votes
0
answers
209
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, ...
- 81
3
votes
0
answers
258
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
0
answers
289
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
2
votes
0
answers
190
views
When does Le Cam's method give tight lower bounds for distribution testing?
In the context of statistical estimation or distribution testing, Le Cam's method is a way to prove lower bounds on the minimax sample complexity ([1,2,3,4], further details below). My question is: ...
- 33
2
votes
0
answers
141
views
How is the Cauchy-Schwarz equality and the assumption on the support of $g$ used to derive this bound?
I am currently reading On Uniqueness Properties of Solutions of Schrödinger Equations and a having trouble understanding a claim made on page 1819.
Context from the paper: let $g\in C^\infty_0(\...
- 751
2
votes
0
answers
286
views
Extension of the Gershgorin circle theorem for symmetric matrices and localization of positive eigenvalues
In mathematics, the Gershgorin circle theorem can be used to localize eigenvalues of a matrix (including symmetric). Let $A$ be a real symmetry $n × n$ matrix, with entries $a_{ij}$. For $i∈{1,…,n}$ ...
- 145
2
votes
0
answers
204
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 ...
- 109
2
votes
0
answers
150
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 ...
- 608
2
votes
0
answers
329
views
Mertens Bound and the Riemann Hypothesis
Let $M(x)$ denote the Mertens function ($M(x)=\sum_{i=1}^{x}\mu(i)$ where $\mu(i)$ is the Möbius function) and let $\Lambda(i)$ denote the Mangoldt function ($\Lambda(i)$ equals $\log(p)$ if $i=p^{m}$ ...
- 177
2
votes
0
answers
591
views
An interesting sequence of numbers arising from the Riemann hypothesis
A very good coincidence occurred today with me. While just plotting random functions in Mathematica, I entered this command:
...
user167505
2
votes
0
answers
390
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 ...
2
votes
0
answers
65
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 = ...
- 123
2
votes
0
answers
133
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 ...
- 949
1
vote
0
answers
84
views
Obstacles to computing $\pi(n)$ in $O(n^{2/3-\epsilon})$ time
Edit: Apologies, as mentioned in the comments I failed to notice the analytic algorithms that take $O(n^{1/2+\epsilon})$ time, so this question doesn’t make much sense. It’s possible there is a ...
- 1,758
1
vote
0
answers
106
views
What is known about the average growth rate of the denominators of $n$ Egyptian fractions summing to one?
Motivation
In the following question posted here on MO and over at MSE, user Noah Schweber asks about a weighted count on Egyptian fraction representations (EFRs). To that end, he defines the ...
- 4,575
1
vote
0
answers
303
views
Lower bound on the sum of the product of random variables
Let $X_i$ be the $i$-th element of the vector $X=(X_1, ..., X_m)$ of i.i.d. random variables.
I am looking for a lower bound for the expression
$\mathbb{P}((\sum^n_{i=1}\prod^{m_i}_{j=1}(X_j))^2 \geq ...
- 129
1
vote
0
answers
197
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 ...
- 3,929
1
vote
0
answers
32
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 ...
- 111
1
vote
0
answers
45
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. ...
- 6,726
1
vote
0
answers
31
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$)...
- 127
1
vote
0
answers
121
views
A lower-bound on matrix-function with vector product
I am currently trying to show that a sequence of homeomorphisms converges to some limiting homeomorphism using Anderson's the inductive convergence criterion. However I can't explicitly compute the ...
- 4,969
1
vote
0
answers
110
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 ...
- 135
1
vote
0
answers
105
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 ...
- 162
1
vote
0
answers
61
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 ...
- 21
1
vote
0
answers
117
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: \...
- 1,406
1
vote
0
answers
58
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}{\...
- 603
1
vote
0
answers
143
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
1
vote
0
answers
108
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
0
votes
0
answers
43
views
Lower bound for the fractional Sobolev norm of the Hermites function
For $r \in (0, 2)$, I am interested in a lower bound for the quantity :
$$I_r(n) := \int_{\mathbb{R}} |f_n(x)|^2 |x|^{r} dx$$
where $f_n(x) = (-1)^n (\sqrt{\pi} n! 2^n)^{-1/2} e^{x^2/2} \dfrac{d^n}{dx^...
- 183
0
votes
0
answers
46
views
Classifier-specific lower bounds on the misclassification rate in binary classification
Consider a binary classification problem for $(X,Y)$, and let $\hat{f}$ be a proposed classifier. We wish to bound the misclassification rate $P(\hat{f}(X)\ne Y)$. There are many known lower bounds on ...
- 13
0
votes
0
answers
228
views
Is it possible to bound Mertens function $M(n)$ from an inclusion-exclusion formulation?
In this post I proposed a formulation of Mertens function $M(n)$ using the inclusion-exclusion principle, as follows:
$$M(n)=-\pi\left(n\right)+\left(\sum_{p_{i}<\sqrt{n}}\pi\left(\lfloor\frac{n}{...
- 229
0
votes
0
answers
167
views
How many elements have a "small" order in a finite field?
I'm hoping that this is an easy question for someone.
How many elements can we expect to have multiplicative order at most $n^{1/c}$ in one of the finite fields $\mathbb{F}_p$ with $p$ prime with $n \...
- 221
0
votes
0
answers
240
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 ...
- 6,726
0
votes
0
answers
329
views
Lower-bound on expected value of norm of transformation of random vector with iid Rademacher coordinates
Let $n$ be a large positive integer. Let $A$ be a positive-definite matrix such with eigenvalues $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$ such that $\lambda_n = o(1) \to 0$ and $\lambda_i=\...
- 6,726
0
votes
0
answers
125
views
Spread of a disease on a modular chessboard (torus) - lower bound
I learned about the following result from one of Peter Winkler's books:
It is impossible to infect the entire $n\times n$ chessboard (usual chessboard) starting from fewer than $n$ infected cells.
The ...
- 1
0
votes
0
answers
236
views
Lower bound of exponential sum
This question is a close cousin of the following:
Lower bound on exponential sums
Let $\phi:[0,1]\to \mathbb R$ be a smooth function with $\frac 1 {10}<\phi'< 10, \frac 1 {10}<\phi''< 10$. ...
- 751
0
votes
0
answers
91
views
Upper bounding the sum with hypergeometric and binomial probabilities
Could you please help me upper bound this tricky expression:
$$P(A)=\sum_{i=0}^n{\left( 1 - \dfrac{\binom kq \binom {n-k}{i-q}}{\binom {n}{i}} \right)}^I \binom ni p^i {(1-p)}^{n-i}$$.
So far I only ...
- 1
0
votes
0
answers
225
views
Bounding the absolute value of a complex integral
I'm working on some problems involving Fourier transforms and convolution problems and there is one problem I cannot solve. In my situation we have a complex valued function $f(ix)$, with $x\in\mathbb{...
- 129
0
votes
0
answers
64
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 ...
- 2,236
0
votes
0
answers
228
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 ...
- 1,133
0
votes
0
answers
99
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 ...
- 608
0
votes
0
answers
130
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,433