Shulou(Shulou.com)11/24 Report--

In the 4th century AD, the Greek mathematician Pappus of Alexandria discovered that the hexagonal structure of honeybee hives seemed to be the best way to divide two-dimensional space into equal and smallest perimeter cells (cells), which allowed bees to reduce the amount of beeswax they needed to produce.

For a single circle, the same area has the smallest perimeter, but when arranged together, there will be gaps, so it is not as economical as hexagons.

But for thousands of years, no one could prove that hexagons were optimal, until 1999, when mathematician Thomas Thomas Hales finally proved that there was no better shape than hexagons. As for 3 and higher dimensions, mathematicians still don't know which shapes of cells are the most "economical" way of tiling.

This problem (called the bubble problem) has been proved to have a wide range of applications. Physicists can study the properties of these "bubbles (cells)", chemists can analyze the structure of crystals, mathematicians can explore the arrangement of spheres, and statisticians can develop effective data processing techniques.

Most importantly, the bubble problem is also deeply related to computer science, with which computer scientists can find a new high-dimensional shape with a minimum surface area. But this shape lacks an important thing, the basis of geometry. Because its existence is proved by computer science and technology, its actual geometry is difficult to grasp. That's what Oded Regev, a computer scientist at New York University, tried to solve in a certificate posted online last month.

Now, what if we make a slight change to the "bubble problem" and only allow space to be divided according to the so-called integer lattice (integer lattice)?

First of all, we need to know what lattice is. In geometry and group theory, the "lattice" in the real coordinate space R ^ n is a set of infinite points in this space, which has the property that the addition or subtraction of two points in the lattice will produce another lattice point, and there is a minimum distance between the lattice points. and each point in the space is within the maximum distance of a lattice point. To put it simply, if the end of a vector in a space is regarded as a point, then a lattice is a set of discrete points with some rules in a space, or it can be said that a lattice is a discrete subgroup with addition operations in a space.

The simplest lattice in dimensional space is the integer lattice. The simplest integer lattice is the space composed of equal base vectors based on Cartesian coordinate system. Lattices have many important applications in pure mathematics, especially in lie algebra, number theory and group theory.

Back to the question, let's take a square array of equidistant points (each point is spaced by 1 unit) and make each lattice point the center of the shape, like this:

The question now is, when the space is tiled in this way (the lattice must be in the center of each cell), what will be the minimum surface area? We call this problem the cubic Bubble problem (Cubical Foams). This problem can help researchers understand the properties of topological spaces called manifolds.

In the case of a square, the area is 1 and the perimeter is 4:

The square tiles the two-dimensional space along the grid, but the perimeter is not the smallest.

For regular hexagons, the area is 1 and the perimeter is about 3.72:

Regular hexagons tile two-dimensional space with the smallest perimeter, but along a different mesh (not an integer lattice).

For non-regular hexagons (choe's irregular hexagons), the area is 1 and the perimeter is about 3.86:

In 1989, mathematician Jaigyoung Choe proved that these hexagons are best tiled along the square in two-dimensional space:

This is also interesting geometrically because it changes the meaning of "optimal". For example, in two-dimensional space, if regular hexagons can only move integer units horizontally and vertically, they cannot be tiled on a plane.

Regular quadrilaterals can. But is this the best way? Jaigyoung Choe found in 1989 that the ideal shape is a hexagon, which is flattened in one direction and elongated in the other. These differences may seem trivial, but in the higher dimensions, they will be obvious.

Of all the shapes with a given volume (two-dimensional space is area), the smallest shape of the surface area (perimeter in two-dimensional space) is a sphere (the circle corresponding to two-dimensional space). With the increase of dimension n, the surface area of the sphere increases proportionally with the root sign n.

But the sphere cannot tile the space without leaving a gap. And an n-dimensional cube with volume 1 can. The problem is that its surface area is 2n, which is proportional to its dimension. A 10,000-dimensional cube with a volume of 1 has a surface area of 20,000.

So the researchers wondered if they could find a "spherical cube" (spherical cube)-a shape that tiled n-dimensional space like a cube, but its surface area grew as slowly as a sphere.

This seems unlikely.

Now we know that this is not the case.

The difficulty of the problem for decades, the cube bubble problem (the cubical foam problem) has been relatively unexplored in high dimensions. The first researcher to make progress in this area is not from the field of geometry, but from theoretical computer science. At that time, computer scientists were looking for a way to prove a UG conjecture (unique games conjecture) in the computer neighborhood field. UG conjecture is the biggest unsolved problem in theoretical computer science at present.

If UG's conjecture is correct, then researchers will be able to understand the complexity of a large number of other computing tasks at once.

Mathematicians believe that a shape called the Weaire-Phelan structure lays out three-dimensional space with the smallest surface area. Although they have not yet proved this point, physical experiments support this hypothesis. Researchers at Trinity College Dublin, Ireland filled a special mold with soap bubbles and found that soap bubbles were naturally arranged in a Weaire-Phelan pattern.

Computer scientists usually classify tasks according to whether they can be solved by an effective algorithm (or whether it is a NP puzzle). For example, the traveling salesman problem is the NP problem (NPH)

The traveling salesman question says that if a traveling businessman wants to visit n cities, he must choose the path he wants to take. The limit of the path is that each city can only visit once and eventually return to the original city. The goal of path selection is that the path distance to be obtained is the minimum of all paths.

The graph coloring problem is also a NP problem. It turns out that finding approximate solutions to many of these tasks is a NP problem.

Shortly after the UG conjecture was proposed, the researchers found that if the conjecture is correct, then the difficulty threshold of any constraint satisfaction problem (constraint satisfaction problem) can be easily calculated. So theoretical computer scientists began to prove UG's conjecture that the task eventually led some of them to discover the spherical cube.

In 2005, O'Donnell and others worked together to solve the UG conjecture problem. They start with a problem about graphics, that is, the so-called maximum cutting problem (max-cut). When a graph is given, how to divide its vertices into two sets in order to make the number of edges connecting the two sets as large as possible.

If UG's conjecture is true, it means that given some random graphs, an effective approximation algorithm can only get less than 87% of the real maximum cut of the graph. If you want to get more than 87%, it is a NP problem.

O'Donnell is going in the opposite direction: he wants to prove that maximum cuts are difficult to approximate, and then use it to prove UG's conjecture. Their plan relies on a method called parallel repetition (parallel repetition), a way to make the problem more difficult.

Suppose you know that distinguishing "a problem you can solve from a problem you can basically solve" is a NP puzzle. Parallel repetition allows you to get a more difficult result on this basis: distinguishing a problem you can solve from a problem you can hardly solve is also a NP puzzle.

But there is one problem. Parallel repetition does not always magnify the difficulty of the problem as computer scientists hope. Some aspects of the maximum cutting problem "create a big problem for parallel repetition, which seems to help to associate maximum cutting with UG's conjecture.

First, the researchers tried to understand parallel repetition in the case of a simple maximum cut. Consider an odd number of vertices connected by edges to form a ring.

You want to mark each vertex with one of the two colors so that the colors of the adjacent vertices are different. Obviously, it is impossible to have an edge that always connects vertices of the same color. You must delete that edge to break the odd ring. Eventually, you want to minimize the number of edges you need to delete to color the graphic correctly.

Parallel repetition allows you to consider a high-dimensional version of the problem. In the high-dimensional version of this problem, you have to break all the odd rings that appear. O'Donnell needs to prove that as the number of dimensions becomes very large, you have to delete a large number of edges to break all odd rings. If this is true, this will mean that parallel repetition can effectively magnify the difficulty of this "maximum cutting" problem.

Then the team found a strange coincidence that there was a geometric way to explain whether parallel repetition would work as they wanted it to. The secret lies in the surface area of the cube foam.

Their problem boils down to the fact that a spherical cube does not exist-it is impossible to divide a high-dimensional space into cells with a much smaller surface area along an integer lattice. As computer scientists hope, a larger surface area corresponds to the need to remove more polygons from the odd cycle graph.

So in 2007, they published a paper outlining how they plan to use this problem to help attack the UG conjecture. Soon, their hopes were dashed.

Ran Raz, a theoretical computer scientist at Princeton University, has demonstrated several major results about parallel repetition. He decided to analyze the parallel repetition of the odd cycle problem. Raz proved that all odd loops in a graph can be broken by deleting fewer edges. In other words, parallel repetition does not fully magnify the difficulty of the maximum cutting problem. At the same time, Raz's results also imply the existence of a spherical cube, which can tile the shape of n-dimensional space, whose surface area is proportional to the square root of n.

In 2008, researchers proved that spherical cubes were indeed possible.

This leads to the question of geometry. Spherical cubes lack the characteristics that mathematicians like-features that are more specific, easier to define and study, and more suitable for potential applications. Geometry has great potential. We just don't know enough about it.

This article comes from the official account of Wechat: Lao Hu Shuo Science (ID:LaohuSci). Author: I am Lao Hu.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.