For $x \in \mathbb{Q}^n$ and $\langle x \rangle$ its encoding length, show: $||x||_1 \leq 2^{\langle x \rangle -n} - 1$.

40 Views Asked by At

I'm trying induction on the dimension $n$, based on the (given) inequality $|y| \leq 2^{\langle y \rangle -1} - 1$ for $y \in \mathbb{Q}$.

Let $\mathbb{Q}^n \ni x = (x_1,...,x_{n-1},x_n)$, and $\mathbb{Q}^{n-1} \ni x' = (x_1,...,x_{n-1})$.

For $n=1$, the statement is just the inequality I cited above.

Assume the statement is true for dimensions greater than $1$ and less than $k$. We have:

$||x||_1 = ||x'||_1 + |x_k| \\ \leq 2^{\langle x' \rangle - k + 1} - 1 + 2^{\langle x_k \rangle} - 1 {\text{ (by the induction hypothesis)}} \\ \leq 2^{\langle x' \rangle - k + 1}\cdot2^{\langle x_k \rangle} - 1 {\text{ (true for $k \geq 2$)}}\\ = 2^{\left(\sum_{i \in [k-1]}\langle x_i \rangle \right) + \langle x_k \rangle - k + 1} -1 \\ = 2^{\left(\sum_{i \in [k]}\langle x_i \rangle \right) - k + 1} - 1 \\ = 2^{\langle x \rangle - k + 1} - 1,$

which is almost what I want, except the extra "$1$" in the exponent. Can I just cross it out after the inequality "$...\leq 2^{\langle x' \rangle - k + 1} - 1 + 2^{\langle x_k \rangle} - 1$" ?

===========

Edit: I was being careless and forgot to add an extra "$-1$" that should have been there in the exponent. Everything's good now.