Proving The Hamming Metric: Open Subsets and Basis of X

[micromass]

So, did you figure out why

$$\sum_{k=0}^{+\infty}{\frac{x_k}{2^k}}<1$$

if one of the x_k is 0?

 

[Metric_Space]

Isn't it because that means the sum above is the difference of two other sums?

 

[micromass]

Isn't it because that means the sum above is the difference of two other sums?

I'm not sure what you mean. Which other sums?

 

[Metric_Space]

one that sums to one, and one that has a zero at the kth entry?

 

[micromass]

Yes, indeed!

So, now we have shown that only (1,1,1,...) has the property that

$$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=1$$.

So, can you now describe the ball around (0,0,0,...) with radius 1?

 

[Metric_Space]

Would it be all entries are 1? But it wouldn't be finite...would it?

 

[micromass]

Would it be all entries are 1? But it wouldn't be finite...would it?

No, this isn't correct. I want you to find the set

$$\left\{(x_1,x_2,x_3,...)~\mid~\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}<1\right\}$$

So...

 

[Metric_Space]

Isn't that just all the (x_1,x_2, ...) minus the entry with (1,1,1,1...)?

 

[micromass]

Indeed, so the ball around (0,0,0,...) with radius 1 is everything except (1,1,1,1,...).
So, now the obvious generalization: what is the ball around $(a_1,a_2,a_3,...)$ with radius 1?

 

[Metric_Space]

would it be everything but (a_1,a_2, a_3, ...)?

 

[micromass]

Uuh, no, I get the impression that you're just guessing here.

Obviously a=(a₁,a₂,a₃,...) will be in the ball, since d(a,a)=0<1.
Moreover, we have just calculated that the ball around (0,0,0,...) is everything but (1,1,1,...). Thus (0,0,0,...) is in the ball...

 

[Metric_Space]

...I think I'll need another hint

 

[micromass]

For what sequence $(x_n)_n$, does

$$\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=1$$

It's basically the same as my last question (when the a_k were simply 0). What must hold for |x_k-a_k| in order for the above series to be 1?

 

[Metric_Space]

|X_k-a_k| --> 0 as k--> infinity?

 

[micromass]

|X_k-a_k| --> 0 as k--> infinity?

No. I don't know how you got that?
You do know that $\frac{1}{2^k}|X_k-a_k|\rightarrow 0$, but I fail to see how it is relevant here...

 

[Metric_Space]

Oh...does |X_k-a_k|=1 for k=1..infinity?

 

[micromass]

Yes! Very good!

So, if |x_k-a_k|=1, then what will x_k be? (Remember that x_k and a_k can only take on 0 and 1 here).

 

[Metric_Space]

x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?

 

[micromass]

x_k=1, a_k=0 or a_k=1,x_k=0 ...is that right?

Very nice! So, basically, a_k has the opposite value of x_k...
Remark that this correspons nicely with the previous thingies where a was (0,0,0,...), then x was (1,1,1,...).

So, the ball around a with radius 1 is just everything except the "opposite of a")!

Now, we're going to make it a little harder. We're going to figure out what the ball around (0,0,0,...) is with radius 1/2. So, for which vectors does

$$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}<\frac{1}{2}$$

As above, you may remark that it suffices to calculate when equality holds, thus

$$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=\frac{1}{2}$$

Since if x has a distance of 1/2 of 0, then all vectors with less 1's than x, have distance <1/2. And this is exactly what we wanted...

 

[Metric_Space]

Would (x_1,x_2,x_3...) = (0,1,1,...)?

 

[micromass]

Would (x_1,x_2,x_3...) = (0,1,1,...)?

Yes that's good, but there is one more possibility!

 

[Metric_Space]

oh right...or (1,0,0,0..)

 

[micromass]

Yes, very good! So elements in the ball around 0 with radius 1/2 consist of those elements with more zeroes than either (1,0,0,...) or (0,1,1,...).

Now, can you describe the ball around an arbitrary a with radius 1/2?

 

[Metric_Space]

balls of radius (1/2)^k have elements

with 1's starting in the kth position and 0's afterwards OR 1's in the (K+1)st position...right?

 

[micromass]

balls of radius (1/2)^k have elements

with 1's starting in the kth position and 0's afterwards OR 1's in the (K+1)st position...right?

No, but you have the right idea. What you describe are the sequences such that

$$\sum_{k=1}^{+\infty}{\frac{x_k}{2^k}}=\frac{1}{2^n}$$

To describe the balls, you'll need < instead of =. So the balls would be the elements which has less 1's than the elements that you describe.

Also, that only describes the balls around 0. It would be fun if you would find the balls around arbitrary elements...

 

[Metric_Space]

around an arbitrary element...wouldn't it be similar to before.

ie. (sum,k=1..infinity, (x_k-a_k)/2^k) < (1/2)^n

either x_k is with 1's starting in the kth position and 0's afterwards
and a_k is ..not sureOR 1's in the (K+1)st position

and a_k is not sure

 

[micromass]

Well, the balls around a with radius 1/2 are either:

1) elements which agree with a in it's first coordinate
2) elements which agree with a except possibly in it's first coordinate.

Can you see why?
Can you extend this to balls with radius (1/2)^k??

 

[Metric_Space]

no...I don't follow

 

[micromass]

Can you see why it is true for a=0?

 

[Metric_Space]

I think so?

 

[micromass]

OK, npw apply the same reasoning to arbitrary a instead of 0...

 

[Metric_Space]

...I think I need a hint

 

[micromass]

Well, when does

$$\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=\frac{1}{2}$$

??

 

[Metric_Space]

x_k=(1,0,0,0,0...) and a_k=(0,0,0,...)

or

x_k=(0,1,0,0...) and a_k=(0,0,0,...)

or

a_k=(1,0,0,0,0...) and x_k=(0,0,0,...)

a_k=(0,1,0,0...) and x_k=(0,0,0,...)

 

[micromass]

No, can you show my how you got that?

If

$$\sum_{k=1}^{+\infty}{\frac{|x_k-a_k|}{2^k}}=\frac{1}{2}$$,

then what must hold for $|x_k-a_k|$.