# Relation between two different functionals: $\lVert p^{-\max}_{-\varepsilon}\rVert$ and $\kappa_{p}^{-1}(1-\varepsilon)$

Given a non-negative sequence $$p=(p_i)_{i\in\mathbb{N}}\in \ell_1$$ such that $$\lVert p\rVert_1 = 1$$,we define the two following quantities, for every $$\varepsilon \in (0,1]$$.

1. Assuming, without loss of generality, that $$p$$ is non-increasing, let $$k \geq 1$$ be the smallest integer such that $$\sum_{i\geq k} \leq \varepsilon$$. Then we define $$\Phi(\varepsilon, p) := \left( \sum_{i=2}^{k-1} p_i^{2/3} \right)^{3/2} \tag{1}$$ i.e., the $$2/3$$-quasinorm $$\lVert p_{-\varepsilon}^{-\max{}} \rVert_{2/3}$$ of the vector $$p^{-\max{}}_{-\varepsilon}$$ obtained by removing the largest element and the $$\varepsilon$$-tail of $$p$$.
2. Defining, for $$t>0$$, the $$K$$-functional between $$\ell_1$$ and $$\ell_2$$ $$\kappa_p(t) = \inf_{a+b=p} \lVert a\rVert_1 + t \rVert b\rVert_2$$ and letting $$\Psi(\varepsilon, p) := \kappa_p^{-1}(1-\varepsilon) \tag{2}$$ (right inverse, IIRC)

then can we prove upper and lower bounds relating (1) and (2)? Recent works of Valiant and Valiant [1] and Blais, Canonne, and Gur [2] imply such relation [see at the end] in a rather roundabout way (for $$p$$'s nontrivially point masses, i.e., say, $$\lVert p\rVert_2 < 1/2$$) (by showing both quantities "roughly characterize" the sample complexity of a particular hypothesis testing problem on $$p$$ seen as a discrete probability distribution), but a direct proof of such a relation isn't known (at least to me), even only a loose one.

Is there a direct proof relating (upper and lower bounds) $$\Phi(\cdot, p)$$ and $$\Psi(\cdot, p)$$, of the form $$\forall p \text{ s.t. } \lVert p\rVert_2 \ll 1,\forall x, \qquad x^\alpha \Phi(c x, p) \leq \Psi(c x, p) \leq x^\beta \Phi(C x, p)$$ ?

A third related quantity, the $$Q$$-norm: [2] (following some previous work of Montgomery-Smith [3]) does show a relation between (2) and a third quantity interpolating between $$\ell_1$$ and $$\ell_2$$ norms, $$T\in\mathbb{N} \mapsto \lVert p\rVert_{Q(T)} := \sup\{ \sum_{j=1}^T \left( \sum_{i\in A_j p_i^2 }\right)^{1/2} A_1,\dots,A_T \text{ partition of }\mathbb{N}\} \tag{3}$$ as, for all $$t>0$$ such that $$t^2\in \mathbb{N}$$, $$\lVert p\rVert_{Q(t^2)} \leq \kappa_p(t) \leq \lVert p\rVert_{Q(2t^2)}.$$

The inequalities established in a roundabout way: The relation between the two quantities shown by combining [1] and [2] (which both establish sample complexity upper and lower bounds for the same hypothesis testing problem) can be rewritten as $$\forall p, \forall \varepsilon \in(0,1/9),\qquad 1\vee \Phi(9\varepsilon,p) \lesssim 1\vee \Psi(\varepsilon,p) \lesssim 1\vee \frac{\Phi(\varepsilon/32,p)}{\varepsilon} \tag{4}$$ where $$\lesssim$$ is an inequality, up to some (absolute) positive constant factor.

[1] Gregory Valiant and Paul Valiant. An Automatic Inequality Prover and Instance Optimal Identity Testing. SIAM Journal on Computing 46:1, 429-455. 2017.

[2] Eric Blais, Clément Canonne, and Tom Gur. Distribution testing lower bounds via reductions from communication complexity. ACM Transactions on Computation Theory (TOCT), 11(2), 2019.

[3] Stephen J. Montgomery-Smith. The distribution of Rademacher sums. Proceedings of the American Mathematical Society, 109(2):517–522, 1990.

$$\newcommand{\vp}{\varepsilon}$$ $$\Psi$$ is not majorized by $$\Phi$$. Indeed, let $$p=(1,0,0,\dots)$$ and $$\vp\in(0,1)$$. Then $$\Phi(\vp,p)=0$$, whereas $$\kappa_p(t)=1\wedge t:=\min(1,t)$$ for $$t>0$$ and $$\Psi(\vp,p)=1-\vp$$.
• That's true, and I should have seen that coming. The relations above basically all assume the quantities are at least some small constant, which I assume should follow from assuming that $p$ is not a point mass (i.e., assuming $\lVert p\rVert_2 < 1/2$ or so) May 21, 2019 at 0:05
• In your edit, what do you mean by $\ll1$? May 21, 2019 at 1:53
• Bounded away from one: at most $c$ for a sufficiently small constant $c>0$. May 21, 2019 at 2:22