1
$\begingroup$

I originally had posted this question on Math.SE, two weeks ago. Since it is research-based (even though I am not 100% confident it fits the bill for MathOverflow) and didn't receive any answer on Math.SE in spite of two consecutive bounties, I am reposting it here -- hoping that's alright.

  • Short version:

For any $n\in\mathbb{N}$, Let $$ p_n(k) \stackrel{\rm def}{=} \frac{1}{(k+1)\ln(k+1)}, \qquad 1\leq k\leq n-1 $$ and consider $$ \kappa_{p_n}(t) = \inf\{ \lVert u\rVert_1+t\lVert v\rVert_2 : u\in\ell_1, v\in\ell_2\text{ s.t. } u+v=p_n\} $$ For a fixed small constant $\varepsilon\in(0,1)$, what is the asymptotic expression (as $n\to\infty)$ of $t=t(n,\varepsilon)$ such that $$\kappa_{p_n}(t) =(1-2\varepsilon)\sum_{k=2}^n \frac{1}{k\ln k} \tag{$\dagger$} $$?

  • Long version:

Recall that for any sequence $p\in\ell_1+\ell_2$, we can defined the K-functional (between $\ell_1$ and $\ell_2)$ as the concave, non-decreasing function $\kappa_p\colon(0,\infty)\to(0,\infty)$ $$ \kappa_p(t) = \inf\{ \lVert u\rVert_1+t\lVert v\rVert_2 : u\in\ell_1, v\in\ell_2\text{ s.t. } u+v=p\} $$ (see e.g. this previous question for more properties).

It is also known (for the continuous case $L_1+L_2$, but I am pretty sure the proof extends to the discrete case) that for any given $t>0$ an optimal decomposition $(u_t,v_t)$ yiedling the value $\kappa_p(t)$ is of the form (assuming wlog that $p\geq 0$) $$ v_t = \min(p, \lambda_t), \qquad u_t = p-v $$ for some threshold $\lambda_t \geq 0$.


This being said, I have been repeatedly failing to find a tight enough (possibly asymptotic with regard to $n$) expression for $\kappa_{p_n}(t)$, where $(p_n)_n$ is a sequence of probability distributions defined as $$ p_n(k) \stackrel{\rm def}{=} \frac{1}{c_n}\cdot \frac{1}{(k+1)\ln(k+1)}, \qquad 1\leq k\leq n-1 $$ and $0$ for $k\geq n$; where $c_n \stackrel{\rm def}{=}\sum_{k=2}^n \frac{1}{k\ln k}$ is a normalizing constant satisfying $c_n = \ln\ln n - K+o(1)$ for some constant $K$ (which can be found, e.g., via Euler—MacLaurin).

More specifically, my end goal would be to find an asymptotic equivalent (or even expansion to lower order terms) to the value $t^\ast(n,\varepsilon)$ solution of the equation $$ \kappa_{p_n}(t) = 1-2\varepsilon \tag{1} $$ where $\varepsilon \in (0,1/2)$ is to be thought of as a small constant.

I tried to tackle that by (i) finding an expression or sufficiently good asymptotic expansion of $\lVert u_\lambda\rVert_1+t\lVert v_\lambda\rVert_2$ (for fixed $t$, as a function of $\lambda$), (ii) minimizing this w.r.t. $\lambda$ to find an expression (or sufficiently good asymptotic expansion) of $\kappa_{p_n}(t)$; and (iii) solve (1) approximately using the expression of (ii) in lieu of $\kappa_{p_n}(t)$.

However, I was stuck at (i) for the discrete case; trying to consider the $L_1+L_2$ analog instead (continuous case) for a start, I got stuck at either (ii) or (iii) -- I am unclear which, as repeating the computations kept giving me either different results or nonsense.

Any clue, idea, or suggestion on what I could do (or what the "right" approach and answer are)?


  • Additional: The answer to $(\dagger)$ (and of (1)), even though not to the more general question of the asymptotic of $\kappa_{p_n}(t)$, should satisfy $$ e^{(\ln n)^{\frac{1}{2}-c'\varepsilon}} \leq \kappa_{p_n}^{-1}(1-2\varepsilon) \leq e^{(\ln n)^{\frac{1}{2}-c\varepsilon}} \tag{2} $$ where $c,c'>0$ are absolute constants; leading me to conjecture that $\kappa_{p_n}^{-1}(1-2\varepsilon) = e^{(1+o(1))(\ln n)^{\frac{1}{2}-c\varepsilon}}$ for some absolute constant $c>0$.

The reason for (2) is rather long-winded, but basically follows from a distribution testing question. [VV14] and [BCG17] both established bounds on the complexity $\Phi$ of a specific problem ("identity testing"), which for arbitrary discrete distribution $p$ and $\varepsilon \in(0,1]$ are respectively $$ \Omega\left(\frac{\lVert p^{-\max}_{-\varepsilon}\rVert_{2/3}}{\varepsilon^2}\right)\leq \Phi(p,\varepsilon) \leq O\left(\frac{\lVert p^{-\max}_{-\varepsilon/16}\rVert_{2/3}}{\varepsilon^2}\right) \tag{3} $$ and $$ \Omega\left(\frac{\kappa_{p_n}^{-1}(1-2\varepsilon)}{\varepsilon}\right)\leq \Phi(p,\varepsilon) \leq O\left(\frac{\kappa_{p_n}^{-1}(1-\frac{\varepsilon}{9})}{\varepsilon^2}\right). \tag{4} $$ Without delving into exactly what the functional $p\mapsto \lVert p^{-\max}_{-\varepsilon}\rVert_{2/3}$ in (3) is (it is the $2/3$-norm of a vector obtained from $p$), computing its asymptotics for $(p_n)_n$ is easier than that of $\kappa_{p_n}^{-1}(1-2\varepsilon)$. By doing so (assuming I didn't make a mistake in the computation), and putting together the inequalities (3) and (4), we get the inequalities from (2).


[VV14] Gregory Valiant and Paul Valiant. An automatic inequality prover and instance optimal identity testing. In Proceedings of FOCS, 2014.

[BCG17] Eric Blais, Clément L. Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. In IEEE Conference on Computational Complexity (CCC), 2017.

$\endgroup$
4
  • $\begingroup$ Doubt. For the usual sequence spaces, $\ell_1\subset \ell_2$, so $\ell_1+\ell_2=\ell_2$. So I wonder if you really mean the usual $\ell_1$ and $\ell_2$. $\endgroup$ – Pietro Majer Jun 5 '17 at 15:05
  • $\begingroup$ Also, I guess $a$ is the same as $p$ $\endgroup$ – Pietro Majer Jun 5 '17 at 15:09
  • $\begingroup$ The usual sequence spaces. I am still mentioning both to make the connection to this functional, which gives in this case a norm on $\ell_2$. $\endgroup$ – Clement C. Jun 5 '17 at 15:10
  • $\begingroup$ Yes, a is a typo and should be p. Thanks for spotting it! $\endgroup$ – Clement C. Jun 5 '17 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.