4
$\begingroup$

Here, everything takes place in $\mathbb{C}^d$ for some $d$, and the sphere $\mathcal{S} = \{\mathbf{x}\in\mathbb{C}^d:\|\mathbf{x}\| = 1\}$.

Given $\delta > 0$, consider a collection of vectors $\mathcal{Y}_{\delta}\subset\mathcal{S}$ such that for every $\mathbf{x}\in\mathcal{S}$ there is a $\mathbf{y}\in\mathcal{Y}_{\delta}$ such that $|\langle \mathbf{x},\mathbf{y}\rangle| > 1-\delta$. Consider now two vectors $\mathbf{v},\mathbf{w}\in\mathcal{S}$ such that $|\langle \mathbf{v},\mathbf{w}\rangle| < \epsilon$ for some small (but fixed) $\epsilon$ (i.e. the vectors $\mathbf{v}$ and $\mathbf{w}$ are "far away."). I would like to show that for every sufficiently small $\delta$ (independent of $\epsilon$) there is a $\mathbf{z}\in\mathcal{Y}_{\delta}$ such that $|\langle \mathbf{v},\mathbf{z} \rangle| > 1-\delta$ (this can be $1$ minus a constant times $\delta$ if that makes it easier) and $|\langle \mathbf{w},\mathbf{z}\rangle| \geq |\langle \mathbf{v},\mathbf{w}\rangle|.$

[Start Later Comment:] To clarify, I would like to see that the result holds for any collection $\mathcal{Y}_{\delta},\,\delta>0$ with the above property (designing your own $\mathcal{Y}_{\delta}$s is not allowed.). Although if one can design such $\mathcal{Y}_{\delta}$s with finite cardinalities so that the above result holds, that would also be interesting. [End Later Comment]

I feel I do not have the necessary tools to approach these kind of problems so any general suggestion would be great.

For some intuition, suppose everything were real and $d=2$ (i.e. we work in $\mathbb{R}^2$). Then $\mathcal{Y}_{\delta}$ could be chosen to be the vectors on the unit circle that are $O(\delta)$-apart. Given $\mathbf{v}$ and $\mathbf{w}$ that are sufficiently far away, I can find a vector $\mathbf{z}$ in $\mathcal{Y}_{\delta}$ that is $1-\delta$ close to $\mathbf{v}$, but at the same time, $\mathbf{z}$ can be chosen to be closer to $\mathbf{v}$ than it is to $\mathbf{w}$.

Edit: It seems there is some confusion regarding the quantifiers. It is fine if you can prove it for a given $\epsilon$ (you can pick $\epsilon = 0.1$, for example.). The problem is then: Given an arbitrary collection of set of vectors $\mathcal{Y}_{\delta},\,\delta > 0$ that satisy $\exists \delta_0 > 0,\,\forall \delta \in (0,\delta_0),\,\forall \mathbf{x}\in\mathcal{S},\,\exists\mathbf{y}\in\mathcal{Y}_{\delta},\,|\langle \mathbf{x},\mathbf{y}\rangle| > 1-\delta.$ Then show, (with $\epsilon = \frac{1}{10}$ for example), that $\exists \delta_0 > 0,\,\forall \delta \in (0,\delta_0),\,\forall \mathbf{v},\mathbf{w}\in\mathcal{S}$ with $|\langle \mathbf{v},\mathbf{w}\rangle| < \frac{1}{10}$ there exists $\mathbf{z}\in\mathcal{Y}_{\delta}$ with $|\langle \mathbf{v},\mathbf{z} \rangle| > 1-\delta$ and $|\langle \mathbf{w},\mathbf{z}\rangle| \geq |\langle \mathbf{v},\mathbf{w}\rangle|$.

$\endgroup$
12
  • $\begingroup$ 500 repuation? Someone really wants an answer. This is just out of my league man. $\endgroup$
    – Asimov
    Sep 6, 2014 at 23:51
  • $\begingroup$ @Asimov Let's say I am a generous person :) $\endgroup$
    – Lord Soth
    Sep 6, 2014 at 23:56
  • 1
    $\begingroup$ @Lord_Soth And because of that I really really wish I could help you. $\endgroup$
    – Asimov
    Sep 6, 2014 at 23:58
  • $\begingroup$ Does this actually require a complex $d$-sphere? It seems like it goes through just as well if you work with a real $2d$-sphere... $\endgroup$ Sep 7, 2014 at 1:13
  • $\begingroup$ @Semiclassical Of course, if one can transform the problem to real coordinates and solve it in that manner, that is also fine. $\endgroup$
    – Lord Soth
    Sep 7, 2014 at 1:17

3 Answers 3

1
+500
$\begingroup$

We can make the obvious strategy work: push $v$ a little bit towards $w$ and then approximate this vector by a $z\in Y_{\delta}$.

Let me write $\langle v, w\rangle = s = |s|e^{i\alpha}$. Next, let's introduce $$ u = \frac{1}{L} (v+\sigma w) , \quad L = \|v+\sigma w\| ; $$ here, I'm going to choose $\sigma = O(\delta^{1/2})$ later on.

I can now pick a $z\in Y_{\delta}$ with $|\langle z, u \rangle|> 1-\delta$. Observe that this implies that $\|e^{i\beta}z-u\|< (2\delta)^{1/2}$ for suitable $\beta$; for convenience, I will assume that $\beta=0$ (replace $z$ by $e^{i\beta}z$ in the calculations below for the general case). Thus $$ \langle z, w \rangle = \langle u, w \rangle + O(\delta^{1/2}) = \frac{s+\overline{\sigma}}{L} + O(\delta^{1/2}) ; \quad\quad\quad\quad (1) $$ the implied constant in $O(\delta^{1/2})$ is $\sqrt{2}$. This means that if I now set $\sigma=A\delta^{1/2}e^{-i\alpha}$ with a sufficiently large $A>0$, then I have satisfied your second condition. Indeed, with this choice of $\sigma$, we have that $$ L^2 = 1 + A^2\delta + 2A|s|\delta^{1/2} , \quad\quad\quad\quad (2) $$ so if we take another look at (1), we see that I have made the scalar product $s$ larger by adding $\overline{\sigma}$, and the error terms coming from $L-1$ and $O(\delta^{1/2})$ can't completely destroy this achievement. More explicitly, notice that $|s+\overline{\sigma}|=|s|+A\delta^{1/2}$, and expand (2): $$ L = 1 + A|s|\delta^{1/2} + O(\delta)\quad\quad\quad\quad (3) $$ Recall that the $O(\delta^{1/2})$ term from (1) was really bounded by $(2\delta)^{1/2}$. Thus $$ \textrm{RHS of (1)} \ge (|s|+A\delta^{1/2})(1-A|s|\delta^{1/2}-O(\delta)) - (2\delta)^{1/2}\\ = |s| +A(1-|s|^2)\delta^{1/2} - (2\delta)^{1/2} - O(\delta) , $$ and this will be $\ge |s|$ for small $\delta>0$, as desired (provided we took $A>0$ large enough).

Finally, consider $$ |\langle v, z\rangle | =\left| L\langle u, z \rangle - \overline{\sigma}\langle w, z\rangle \right| \ge L (1-\delta) - A\delta^{1/2}\left( \frac{|s|+A\delta^{1/2}}{L}+O(\delta^{1/2})\right) . $$ We have one potentially dangerous term on the RHS, namely $-A|s|\delta^{1/2}/L$ (everything else we're subtracting is $O(\delta)$). However, (3) shows that everything will work out fine after multiplying out $L(1-\delta)$.

$\endgroup$
6
  • $\begingroup$ Thanks for the answer! I am struggling though to understand how you derive the second condition (i.e. the arguments before "can't completely destroy that achievement."), as according to my calculations it does not work out as you cannot control the phase of the $O(\sqrt{\delta})$ term. Would you be able to provide more details? BTW, for (2), I guess the last term should have a factor of $\cos\alpha$. $\endgroup$
    – Lord Soth
    Sep 7, 2014 at 2:39
  • $\begingroup$ (2) is correct, with no $\cos\alpha$ term (this will in fact become crucial later on): $\|v+\sigma w\|^2 = \|v\|^2 + |\sigma|^2 \|w\|^2 + 2\textrm{Re }\sigma \langle v, w\rangle$, and the last term is positive (even without the real part) by my choice of the phase of $\sigma$. $\endgroup$
    – user138530
    Sep 7, 2014 at 2:49
  • $\begingroup$ @LordSoth: As for (1), I've made this more explicit now. $\endgroup$
    – user138530
    Sep 7, 2014 at 3:03
  • $\begingroup$ By the way (referring to the revised version of your question), this argument works for any $\epsilon<1$; of course, I only show that $|\langle v, z\rangle |> 1-C\delta$. $\endgroup$
    – user138530
    Sep 7, 2014 at 3:09
  • $\begingroup$ Thanks for the clarifications. The argument seems to work fine, although I will need to get my hands dirty and verify every step again myself - I will let you know. But that $\beta$-trick especially, that is very cool, and thanks for teaching me that! I had a similar approach myself originally (pick $\mathbf{z}$ as a vector that is say $2\delta$ close to $\mathbf{v}$ but also $\delta$ far from $\mathbf{v}$ so that we give the remaining $\delta$-energy to the direction of $\mathbf{w}$), but could not make it work ... $\endgroup$
    – Lord Soth
    Sep 7, 2014 at 3:50
0
$\begingroup$

Intuitive Remark: for two unit vectors $ x \cdot y = |x| |y| \cos \theta = \cos \theta$, so are measuring the angle between the vectors.

  • $|x \cdot y| > 1 - \delta$ is a precise way of saying $x \approx y$.

  • Your $Y_\delta$ is defined so that for any $z \in S$, there is $z \approx y \in Y_\delta$.

  • $|v \cdot w| < \epsilon$ mean essentially $v \perp w$ since their inner product is close to $0$.

  • We would like to find $z \approx v$ with $z$ closer to $w$ then the original $v$.

These types of problems appear in coding theory, such as the Hamming bound.


This seems rather difficult. The condition $w \cdot z = v \cdot w$ is equivalent to $ w \cdot (z - v) = 0$ which defines a plane. All points $z$ on one size of the plane is more similar to $v$ than to $w$.

Then consider the cone $ z \cdot v = 1 - \delta$. The cone, the plane and the sphere define a semi-circle (or hemisphere) and we looking for a $Y_\delta$ point in there.

For every point in that half-sphere, we can find a $Y_\delta$ point approximating it, and will be at most angle $2\delta$ from $v$ by Triangle inequality.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer, perhaps the arguments here could be formalized. $\endgroup$
    – Lord Soth
    Sep 8, 2014 at 19:02
0
$\begingroup$

The statement you are hoping to prove (at least in the form you wrote it in the edits)
is false (already for $d=2$). I will work over the real numbers, but with a minor modification, this example works over the complex numbers as well.

As an example, consider the net $Y_\delta\subset S^1\subset R^2={\mathbb C}$ consisting of roots of unity of the order $4N$. Let $$ \delta= 1- \cos(\frac{\pi}{2N}). $$ By taking $N$ large we can get $\delta$ as small as you wish. Let $$ w=i, v=e^{\frac{i\pi}{10N}}.$$ Then for every $z\in Y_\delta\setminus \{\pm 1\}$, $$ 1- |<z, v>| >\delta. $$ On the other hand, for both $z=\pm 1$, we have $$ |<v, w>| > |<w,z>|=0, $$ which is the opposite inequality of the one you are hoping for.

Edit.

In what follows, I will use the notation $S=S^{2d-1}$ for the unit sphere in the complex vector space ${\mathbb C}^d$, equipped with the standard hermitian metric $\langle \cdot , \cdot \rangle$.

You are interested in the following function on $S\times S$: $$ D(v, w)= 1- |\langle v, w\rangle|. $$ This function is not a metric, but it is comparable to the chordal metric $d$ on the complex-projective space ${\mathbb C} P^{d-1}$, which is given by the formula: $$ d([v], [w])= 1- |\langle v,w\rangle|^2, \quad v, w\in S. $$ Here $[z]$ denotes the projection of a unit vector $z$ in ${\mathbb C}^d$ to ${\mathbb C} P^{d-1}$: $$ z=(z_1, z_2, \ldots, z_d)\mapsto [z]=[z_1: z_2: \ldots : z_d]. $$

Definition. A subset $Y\subset S$ will be called a $\delta$-pet if for every $x\in S$ there exists $y\in Y$ such that $D(x, y)\le \delta$.

Note. Recall that a subset $Y$ in a metric space $(X,d)$ is called an $\eta$-net if for every $x\in X$ there exists $y\in Y$ such that $d(x,y)\le \eta$. Define the function $\Theta(D)$ $$ \Theta(D)=\arccos(1-D)\in [0, \pi/2], \quad D\in [0, 1]. $$ Then a subset $Y\subset S$ is a $\delta$-pet if and only if the projection of $Y$ to the complex-projective space ${\mathbb C} P^{d-1}$ is a $\Theta(\delta)$-net for the angular (Fubini-Study) metric on ${\mathbb C} P^{d-1}$. The latter is given by $$ \angle([v], [w])= \Theta(D(v, w)), \quad v, w\in S. $$

Now, I can state a theorem.

Theorem. There exists $\delta_0>0$ such that for all $\delta\in (0, \delta_0)$, every $\delta$-pet $Y\subset S$ and every $v, w\in S$, there exists $z\in Y$ such that $$ D(z,w) \le D(z,v), $$ while $$ D(z,v)\le 10\delta. $$ One can, in principle, estimate the number $\delta_0$ and reduce the constant $10$ a bit, but I am too lazy for that. As I explained above, you cannot replace the inequality $$ D(z,v)\le 10\delta $$ with $$ D(z,v)\le \delta. $$

I do not know if this theorem is what you are actually asking for.If you are, I can write down a proof. It does use some elementary Riemannian geometry though.

$\endgroup$
3
  • $\begingroup$ You have shown that for most $z$s, $1-|\langle z,v\rangle| > \delta$. Then, you show for some $z$, the second condition does not hold (via your last line). I would like to see that for some $z$, both conditions $1-|\langle z,v\rangle| > \delta$ and $|\langle v,w\rangle| \leq |\langle w,z\rangle|$ hold. Your example is thus not a counterexample to my assertion. I hope that makes it clear. BTW, there is a typo in your last inequality. $\endgroup$
    – Lord Soth
    Sep 8, 2014 at 18:36
  • $\begingroup$ This does show (with the typo corrected) that the $|\langle z, v \rangle | > 1-\delta$ version will not work; you do need a constant as in $\ldots > 1-C\delta$. $\endgroup$
    – user138530
    Sep 8, 2014 at 19:37
  • $\begingroup$ @LordSoth: I was not proving anything for "most $z$'s". What I proved is that the statement I asked you to state is false: I verified it for all $z$'s. See the edit though. $\endgroup$ Sep 9, 2014 at 8:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .