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$
  • $\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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.