Doubts in some inequalities used in asymptotic analysis

I was going through this recent paper, and I had a couple of doubts in the final analysis of complexity of the scheme (you don’t need to go through the whole paper). I included three questions here, as I thought they seem to simple questions.

  1. In Pg 17 (last four lines, see after equation 7), there is this inequality that is used (here, $ k(n) = \sqrt{\frac{n\delta(n)}{\log n}}$ and $ \delta(n) = o(n / \log n)$ ):

$ \frac{\binom{n}{a}}{\binom{^n/_k}{^a/_k}^k} \leq (^n/_k)^k$

Can I know a proof for it?

  1. Similarly, in the beginning of Pg 18, how is this possible? (the above inequality is used to get here though, $ (n / k)^{k / 2}$ thing, and don’t worry about the meaning of $ \mathtt{ss}$ )

$ \mathtt{ss} \leq \sqrt{\binom{n}{\frac{n}{2}-\delta(n)}}\cdot (n / k)^{k / 2} \cdot \binom{k}{2\delta(n)} \cdot 2^{(2\delta(n)+1)n / k} \leq 2^{n / 2 + o(n)}$

  1. Also, this one might be a bit trivial, in Pg 17, one inequality above equation 7, the $ O(n)$ term is dropped, isn’t that relevant?

Bridging between Rosethal Inequalities and log convex tails

Let $ X_1,\ldots,X_n$ be independent with $ \mathbf{E}[X_i] = 0$ and $ \mathbf{E}[|X_i|^t] < \infty$ for some $ t \ge 2$ . Write $ \|X\|_p = (E|X|^p)^{1/p}$ .

Then we have the classical “Rosenthal-type inequalities”: $ $ \left\|\sum_i X_i \right\|_p \le C_1\left(\sqrt{p}\left(\sum_i \|X_i\|_2^2\right)^{1/2} + p\left(\sum_i \|X_i\|_p^p\right)^{1/p}\right), \ \left\|\sum_i X_i \right\|_p \le C_2\frac{p}{\log p}\left(\left(\sum_i \|X_i\|_2^2\right)^{1/2} + \left(\sum_i \|X_i\|_p^p\right)^{1/p}\right) \ \text{and in general} \ \left\|\sum_i X_i \right\|_p \le C_3\min_{s=1}^p\left(\sqrt{s}e^{p/s}\left(\sum_i \|X_i\|_2^2\right)^{1/2} + s\left(\sum_i \|X_i\|_p^p\right)^{1/p}\right) $ $

On the other hand, if $ X_i$ all have logarithmically concave tails; (that is, $ \Pr[X \ge t = e^{−N(t)}]$ for $ t \ge 0$ , where $ N : R_+ \to R_+ \cup\{\infty\}$ is a convex function), then we have the much stronger:

$ $ \left\|\sum_i X_i \right\|_p \le C_4\left(\sqrt{p}\left(\sum_i \|X_i\|_2^2\right)^{1/2} + \left(\sum_i \|X_i\|_p^p\right)^{1/p}\right). $ $ (Note there is no factor $ p$ on the second term.)

My question is thus: Is there a series of results interpolating between the Rosenthal inequalities and the inequalities for heavy random variables?

It creates an odd “discontinuity” that the factor of $ p$ disappears suddenly when the random variables get sufficiently heavy.

Interestingly, for identical random variables we can use the theorem $ $ \left\|\sum_i X_i \right\|_p \le C_5 \sup_{\max\{2,p/n\}\le s\le p}\frac{p}{s}\left(\frac{n}{p}\right)^{1/s}\|X_1\|_s $ $ to show that $ \|X\|_p \le p^c \implies \left\|\sum_i X_i \right\|_p \le C_6(\sqrt{pn} + (n/p)^{1/p}p^c)$ for any $ c>0$ , $ p\le n$ . This can be interpreted as saying that the $ p$ -free version of the above inequalities is true in many cases, even when the random variables aren’t that heavy.

(I should note that all results listed in this question can be found in Rafał Latała’s:

Automating the solution of pairs of polynomial inequalities as a bound

Let’s consider the following pair of quadratic inequalities:

$ $ x^2+x \geq a$ $


$ $ x^2-x < a$ $

The solution of the first inequality is $ $ x \geq \frac{-1+ \sqrt{1+4a}}{2}$ $ or $ $ x \geq \frac{-1- \sqrt{1+4a}}{2}$ $ .

Now, the first one is always going to be larger than the second one, as $ $ \sqrt{1+4a}>0$ $ . So, $ $ x \geq \frac{-1+ \sqrt{1+4a}}{2}$ $ is the “true” lower bound. Therefore, we will consider the solution as:

$ $ x \geq \frac{-1+ \sqrt{1+4a}}{2}$ $ ——> (1)

For the second inequality, the solution is $ $ x < \frac{1+ \sqrt{1+4a}}{2}$ $ or $ $ x < \frac{1- \sqrt{1+4a}}{2}$ $ .

Again, since $ $ \sqrt{1+4a}>0$ $ , the second solution is always going to be smaller than the first solution. So, $ $ x < \frac{1- \sqrt{1+4a}}{2}$ $ is the “true” upper bound.

However, because $ $ \frac{1- \sqrt{1+4a}}{2}$ $ is negative of the solution of the first inequality from (1), we encounter some issues. For example, if the solution in (1) is negative (<0), then its fine. For example, if, say, (1) evaluates to $ $ x \geq -5$ $ , then our solution to the second inequality implies $ $ x<5$ $ , which is fine. But, if the solution in (1) is positive (>0), then the pair of solutions taken together doesn’t make sense. For example, if (1) evaluates to $ $ x \geq 5$ $ , then our solution to the second inequality implies $ $ x<-5$ $ , which is nonsensical.

Therefore, we need to reject this solution for the second inequality and accept the other solution as the true solution:

$ $ x < \frac{1+ \sqrt{1+4a}}{2}$ $ ——> (2)

Thus, from (1) and (2), we can say that the solution of these 2 inequalities given as a bound is:

$ $ x \in [\frac{-1+ \sqrt{1+4a}}{2}, \frac{1+ \sqrt{1+4a}}{2})$ $

As demonstrated, the process of rejecting 2 of the possible solutions can be a bit involved. Also, the process can be different for other sets of inequalities, where the same lines of thinking might not disqualify 2 of the candidate solutions.

I want to be able to automate this process for any pair of inequalities. I have written the following code to solve a set of quadratic polynomial inequalities and return the solution as a bounded set:

from sympy import simplify, degree import math  def extract_terms(LHS, operator, var):     expression = simplify(LHS)     variable  = simplify(var)     poly_degree  = degree(expression, gen=variable)      term_coeffs = []     for x in range(poly_degree,-1,-1):         if x>0:             term = simplify(str(variable)+"**"+str(x))             term_coeffs.append(expression.coeff(term))             expression = simplify(str(expression)+"-"+str(simplify("("+str(term)+")*("+str(expression.coeff(term))+")")))         else:             const_value =  expression             term_coeffs.append(const_value)     return term_coeffs  def solve_quad_inequality(LHS, operator, var):     c, d, e = extract_terms(LHS, operator, var)     try:         s1 = -(d/(2.0*c))+math.sqrt(-(e/c)+(d/(2.0*c))**2)         s2 = -(d/(2.0*c))-math.sqrt(-(e/c)+(d/(2.0*c))**2)         return s1, s2     except:         print('The given inequality does not have a real solution.')         return 0  def give_soln_bounds(LHS_1, operator_1, var, LHS_2, operator_2):     s1a, s2a = solve_quad_inequality(LHS_1, operator_1, var)     print("The candidate solutions for {}{}0 are: {}{}{} or {}{}{}".format(LHS_1, operator_1, var, operator_1, s1a, var, operator_1, s2a))      s1b, s2b = solve_quad_inequality(LHS_2, operator_2, var)     print("The candidate solutions for {}{}0 are: {}{}{} or {}{}{}".format(LHS_2, operator_2, var, operator_2, s1b, var, operator_2, s2b))      a = s1a if s1a>=s2a else s2a     if s1b<s2b:         if s1b>a:             b = s1b         else:             b = s2b     else:         if s2b>a:             b=s2b         else:             b=s1b      print('The bounded solution for the given pair of inequalities is: x ∈ ['+str(a)+', '+str(b)+')')  give_soln_bounds("x**2-5*x+6", ">=", "x", "x**2-5*x+4", "<") 

This gives the following output:

The candidate solutions for x**2-5*x+6>=0 are: x>=3.00000000000000 or x>=2.00000000000000 The candidate solutions for x**2-5*x+4<0 are: x<4.00000000000000 or x<1.00000000000000 The bounded solution for the given pair of inequalities is: x ∈ [3.00000000000000, 4.00000000000000) 

Another example test:

give_soln_bounds("x**2+x-1", ">=", "x", "x**2-x-1", "<") >>>  The candidate solutions for x**2+x-1>=0 are: x>=0.618033988749895 or x>=-1.61803398874989 The candidate solutions for x**2-x-1<0 are: x<1.61803398874989 or x<-0.618033988749895 The bounded solution for the given pair of inequalities is: x ∈ [0.618033988749895, 1.61803398874989) 

It seems to work fine for the examples I have thrown at it so far, but is there any way to know if its truly correct? Any counterexample would be great too!

Also, it can’t handle equations where I give symbolic inputs. For example, $ $ x^2-x-k<0$ $ , where the solution is expected in terms of k. Is there any way to do that?

Another issue is, if I want to this for cubic inequalities, I can foresee a problem with comparing all the 9 possibilities arising from the 3 candidate solutions for each inequality. Is there any way to cut down on the number of comparisons to be made to search for the valid solutions?

And finally, if you see any possible improvement in the code (be it style-wise or performance-wise), please do let me know.

Is there a software to solve function inequalities?

Suppose I have some inequalities that my function (say $ \mathbb R\to \mathbb R$ ) needs to satisfy, like $ \forall x,y\; f(x)+f(y)\le f(x+y)$ and $ f(1)=0$ . Is there some software that can find solutions/prove that there’s no such function?

Of course, the problem is undecidable in general, but this doesn’t rule out some software that could be efficient in practice.

Solve system of inequalities with orthogonality Constraint in Python

I need to solve a system of inequalities for a vector of variables where one of the inequalities has an orthogonality constraint. In my particular problem, it has been proven that solving the system always results in one exact solution. Because of the orthogonality, I don’t think I can use linear programming. Anyone have recommendations for efficient methods to solve in Python? Wolfram alpha is able to do it! (See example here) I know sympy can’t because it only can solve for univariate case. Please include runtime with whatever answer you give!

Inversion inequalities

Do there exist $ n$ permutations $ (\pi_i; 1 \le i \le n)$ of $ [k]$ such that for any transposition $ \sigma = (j, l)$ , $ 1 \le j, l \le k$ , \begin{equation} \label{1} (*) \quad \sum_{i = 1}^n inv(\pi_i \circ \sigma) > \sum_{i = 1}^n inv(\pi_i), \end{equation} where $ inv(\pi_i)$ is the number of inversions of $ \pi_i$ , but \begin{equation} (**) \quad \sum_{i = 1}^n inv(\pi_i \circ \pi) \le \sum_{i = 1}^n inv(\pi_i) \quad \mbox{for some permutation } \pi \neq id ? \end{equation} The answer is no for n = 1 and 2, since $ inv(\pi_i \circ \sigma) = inv(\pi) \pm 1$ for any adjacent transposition $ \sigma$ . In these cases, $ (*)$ implies that $ \pi_i = id$ and $ (**)$ is automatically true. The answer also seems to be negative for $ \pi$ a permutation of adjacent three elements, e.g. $ (2,3,1)$ . I want to know if any positive or negative result holds in general.