How do you find correct eight out of eleven?

A trip into the eleven-dimensional

A useful clue comes from geometry. However, you have to go into the eleven-dimensional space for this, and that seems a bit confusing, at least on the first visit. A point in this space is nothing more than a sequence of numbers (a “vector”) of length 11. So every attempted solution to our strange exam is such a vector of eleven, with components each of which is either 0 or 1.

In our familiar three-dimensional space, the eight vectors whose components are 0 or 1 form a cube. Accordingly, the conceivable exam solutions are the 2048 corners of the »unit cube in eleven-dimensional space«. If two corners of the ordinary cube differ in only one coordinate, then they are connected by an edge. This should also apply to the eleven-dimensional unit cube. Only here eleven edges go out from each vertex.

In order to find one’s way around in this space better, one introduces something like a distance measurement (“metric”). The distance between two corners of the unit cube is defined as the number of edges that you have to traverse to get from one corner to the other – using the shortest route, of course. It is equal to the number of coordinates in which the two eleven vectors differ. It is also called “Hamming distance” after the mathematician Richard Wesley Hamming (1915–1998), who used this concept of distance to construct error-correcting coding. In more familiar terrain, more specifically in the checkerboard layout of downtown Manhattan, such a distance measurement is known as the “cab driver metric”: the distance from A to B is not the linear distance, but the number of trips from intersection to intersection that you have to cover in the road network.

See also  Why mistletoe spreads so rapidly - knowledge

If we have a metric, we can also speak of balls. As in familiar geometry, the sphere is centered M and radius right the set of all points by M the distance at most right to have. Don’t be bothered by the fact that the balls look very angular in the taxi driver metric. And in the eleven-dimensional unit cube you can’t imagine a sphere anyway. Even when mapped into three-dimensional space, the sheer number of points makes things extremely confusing. In order to give at least a certain impression, I limited myself to seven instead of eleven dimensions in the illustration:

© Christoph Pöppe (detail)

Placeholder_MU_1 | In contrast to ordinary spheres (in two dimensions: circles), spheres in the taxi driver metric are so angular that they fit together seamlessly, so to speak. These spheres (blue) with a radius of 2 can be arranged in such a way that no point of the square grid remains untouched. It is enough to continue the drawn pattern in the obvious way.

Why all the talk about square balls in eleven-dimensional space? To look at the task of finding a minimum set of possible solutions, guaranteed to contain eight correct answers, from a new perspective. The aim is to cover the eleven-dimensional unit cube with as few spheres with a radius of 3 as possible. Why Radius 3? If the unknown corner of the cube that corresponds to the correct solution lies in such a sphere, then the center of the sphere deviates from this corner in at most three places, so it is accepted as the solution. But since we don’t know the correct solution, we have to make sure that each corner of the unit cube lies in such a 3-sphere.

See also  "KLIK green": How clinics want to become better for the climate

In the Taxi Driver metric, the task of covering all of Manhattan in bullets is surprisingly easy. One might therefore come up with the idea of ​​arranging spheres symmetrically in some way on the unit cube. That fails.

See more here

Leave a Reply

Your email address will not be published. Required fields are marked *