Assume that the data is restricted to lie in a unit sphere.
(a) Show that is non-increasing in .
Suppose a dichotomy is shattered by a hyperplane with margin then it is also shattered by that hyperplane with margin as there is no margin argument in final hypothesis representation.
(b) In 2 dimensions, show that for .
For each line segment ( and are two endpoints lying on the unit circle), call the center of unit sphere , by The Law of Cosines, we have:
So the line segments and have equal length if and only if , the line segments if and only if .
If then (and ). Now consider the third point lying on the unit circle. Suppose does not cross , then , it’s easy to see that if exceeds then and we still have two points lie within distance of each other, the other case is similar. Now suppose crosses , then , the arguments go similar.
So for any 3 points lying on the unit circle, there must be two that are within distance of each other.
[FROM HERE I WAS FALLEN INTO FALLACY]
In the case that not all 3 points lie on the unit circle, we can consider this simple situation: Suppose does not lie on the unit circle, we define as the intersection of the line and the unit circle, by the Law of Cosines, we always have and , so if () exceeds then () exceeds . The same goes for and if they do not lie on the unit circle. But we have argued that for any 3 points lying on the unit circle, there must be two that are within distance of each other, so this statement is also true for any 3 points inside the unit circle.
So the statement follows.