The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
170 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 ...
2
votes
0answers
70 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 ...
2
votes
1answer
89 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 ...
1
vote
2answers
114 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 ...
3
votes
1answer
342 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.
7
votes
1answer
236 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 ...
0
votes
0answers
91 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} = ...
0
votes
0answers
62 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
vote
0answers
93 views

Bound a sum of a serie defined by a recursive integer function

I'm using a recursive function $f: \mathbb{N} \rightarrow \mathbb{N}$, that is defined as \begin{equation} f(n)=\lceil \log(f(n-1)) \rceil +f(n-1) \end{equation} where $f(1)=F\in \mathbb{N}$, and ...
0
votes
0answers
73 views

Looking for tighter bounds

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 ...
15
votes
1answer
909 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},\ ...
3
votes
2answers
577 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 ...
3
votes
2answers
132 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 ...
2
votes
2answers
322 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 ...
0
votes
1answer
176 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 ...
4
votes
1answer
318 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
votes
0answers
80 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 ...
6
votes
0answers
291 views

Bounding the probability that a random variable is maximal

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 for ...
1
vote
0answers
107 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 ...
6
votes
2answers
372 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)? ...
2
votes
2answers
328 views

lower bound for $\Re\zeta(1+it)$

Hi is there any lower bound for $\Re\zeta(1+it)$. I did try with computer until some ordinate and I saw $\Re\zeta(1+it)>0$. If it is true, is there any reference to prove it. thanks
1
vote
0answers
91 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$ ...
1
vote
0answers
207 views

Geometric/Analytic techniques for constructive and asymptotic bounds in the Lee metric

Slight extension of cross posting from http://cstheory.stackexchange.com/questions/7408/lee-metric-gilbert-varshamov-and-hamming-bounds-for-larger-relative-distance-rang (closed there) The following ...
3
votes
2answers
1k 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?
0
votes
0answers
397 views

Lower bound over a concave function

Hi everyone, I will be to grateful if help me find a tight lower bound $g(x)$ over the following concave function: $$f(x) = \sqrt{1+4x} -1 + \log(\sqrt{1+4x}-1) - \log(2x) \geq g(x),$$ where $x \geq ...
3
votes
2answers
631 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 ...
4
votes
1answer
574 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
1answer
294 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 ...
14
votes
6answers
3k 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)$ ...
2
votes
2answers
1k 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 ...
5
votes
1answer
242 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?
8
votes
0answers
559 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 ...
14
votes
4answers
2k 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 ...