Home  >  Article  >  Technology peripherals  >  Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

PHPz
PHPzforward
2023-10-14 14:17:071056browse

Tao Zhexuan made a new breakthrough in studying the periodic dense paving problem

On September 18, Tao Zhexuan and Rachel Greenfeld published the preprinted paper "Translational Single Mingling Pavement" "Undecidability of translational monotilings" was uploaded to arXiv.

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Paper address: https://arxiv.org/abs/2309.09504

This paper The main conclusion is that if the dimensions of the grid are unbounded, then the problem of determining whether a finite subset of the grid can tile a periodic subset of the grid is undecidable

Be aware that this problem is decidable in dimension 1 and dimension 2.

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Tao Zhexuan said that it is a bit strange that most of the components demonstrated in the article are similar to popular games——

There are dense analogues of dominoes, Sudoku, the computer game "Tetris", and even the children's game "Fizz buzz"

Why study one Why do math problems involve so many games? Terence Tao also cannot explain

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

The undecidability of translational single dense tiling

This paper, It is a sequel to the two's previous paper. Link Periodic Tiles Problem

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

In the last paper, they constructed a high-dimensional gridTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving The translation of the single dense pavement Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

(therefore the single dense pavement Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is a finite set), which is non-periodic (There is no way to "fix" this tile into a periodic tile Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, where Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is now relative to the finite index subgroup Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is periodic).

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

This fact negates the hypothesis of Stein, Grunbaum-Shephard and Lagarias-Wang about the non-existence of aperiodic closely packed monomers

("Hat single dense paving" is a recently discovered non-periodic equidistant single dense pavingTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving. In this kind of single dense paving, it is allowed to use Rotation, reflection and translation, or the newer "ghost monolith". These monoliths are similar to hat monoliths, except no reflection is required).

One of the reasons why Terence Tao and Rachel Greenfeld inspired this conjecture is the observation of mathematician Hao Wang

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

He found that if the periodic tessellation conjecture is true, then the translational tessellation problem is algorithmically decidable——

There is a Turing machine, for Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, when given a dimension Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving and a finite subset Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving At this time, you can determine within a limited time whether Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving can be densely paved Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving.

This is because if there is a periodic tiling, it can be found through a computer search

If there is no tiling at all, Then it can be known from the compactness theorem that there are some limited Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving subsets that cannot be covered by Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving disjoint translations. This can also be done by computer Search to discover.

The periodic tessellation conjecture asserts that these are the only two possible situations, thus giving decidability.

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

On the other hand, Wang’s point of view is immutable: the failure of the periodic tessellation conjecture does not automatically mean that the translational tessellation conjecture The undecidability of the problem, since it does not rule out the existence of other algorithms to determine the tiling that do not depend on the existence of periodic tiling

(e.g. even if With the newly discovered hat and ghost tiling, it is still an open question whether the isometric single tiling problem of polygons with rational coefficients in Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is decidable, whether or not it has reflections.

The main results of this article address this issue (with a caveat):

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

What needs to be rewritten is: Theorem 1

does not exist any algorithm, for Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, given a dimension Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving , a periodic subset Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, and a finite subset Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, which can determine whether there is a translational tiling in a limited timeTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving.


Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

It should be noted that the periodic subset Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving of Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving must be used instead of all Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving ; This is largely due to technical limitations of this approach and is likely to be eliminated with additional effort and creativity.

In addition, Terence Tao and Rachel Greenfeld also noticed that whenTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, the periodic pavement conjecture was established by Bhattacharya, so inTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingIn this case, the problem can be determined.

For any fixed value of Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, it is still open whether the tiling problem is decidable (note that in the above results, the dimension Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is not fixed, but part of the input).

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

This theorem also implies that due to the well-known connection between algorithmic undecidability and logical undecidability (also known as logical independence) It turns out that there exists a (in principle unambiguously describable) periodic subset of the dimensions Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving,# The finite subset Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving of Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving##, so that Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving can be passed through translational tiling Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving cannot be used in ZFC set theory Confirm or falsify (assuming of course that the theory is consistent).

As a result of this approach, we can also use the "almost two-dimensional" group Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving instead of ## here #, where Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is a finite abelian group (now part of the input, instead of dimension Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving). Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Next, some main ideas of the proof are described.

A common way to prove that a problem is undecidable is to "encode" other problems that are known to be undecidable into the original problem, so that any algorithm that determines the original problem can also determine it. Embedded Question

Therefore, we encode Wang’s dense paving problem as a single dense paving problem Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving:

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

The second question is about the Wang’s secret shop problem

Given a limited Wang’s secret shop setTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving(unit (square, each edge assigned a certain color from a limited palette), is it possible to tessellate a plane using a standard gridTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving by translation so that adjacent tiles are in common Have the same color on the edges?

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Berger once famously concluded that this question cannot be determined

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

The content that needs to be rewritten is: Berger, Robert,

Converting this problem into a high-dimensional translational single dense tiling problem requires solving some intermediate problems

First, we can easily embed the Wang's secret shop problem into a similar problem, which we call the domino problem:

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Rewritten as follows: Domino problem is problem 3

Given a level (or vertical) finite set of dominoes Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving or Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, which are a pair of adjacent unit squares, each unit square is represented by a finite set ## To decorate it with an element point in Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving#, is it possible to assign a point to each unit square in the standard lattice tiling Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, so that each pair in this tiling Can horizontal (or vertical) squares use dominoes from Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving or Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving?

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

In fact, we only need to insert each Wang's tile as a separate "point" and define the domino setTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving are pairs of Wang's dense tiles that are adjacent horizontally or vertically and have the same edge color.

In the next steps we will combine the domino problem with the Sudoku problem:

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Question 4 (Sudoku problem)

Given column widthTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving , set of numbers Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, set of functions Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, and "initial conditions" Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving (I won’t go into details here), is it possible to assign a number to each cell Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving in the "Sudoku board" Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving ## so that for any slope Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving and intercept Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, the number Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving# along the Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving line ## is located in Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving (and Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is subject to the initial condition Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving)? Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingThe most novel part of this paper is to prove that the domino problem can indeed be embedded in a Sudoku problem.

Embedding the Sudoku problem into the single dense pavement problem is based on the modification method proposed in previous papers

These papers also proposed Different versions of Sudoku problems, and created a method called "Tab Language" that can transform various problems (including Sudoku problems) into a single Tile Problem

To encode a domino problem as a Sudoku problem, we need to get a domino function

(which obeys the same rules as certain domino sets

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving associated domino constraints) and use it to construct the Sudoku function Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving (which obeys some Sudoku constraints associated with the domino set); conversely, each obeys the Sudoku puzzle rules Sudoku functions must be generated from domino functions in some way. Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

This approach is not immediately obvious, but Tao and Rachel Greenfeld adapted some of Aanderaa and Lewis's ideas with the help of Emmanuel Jeandel, and certain hierarchies were used to encode one question into another.

Here we explain the hierarchical structure Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving (due to the two-dimensional nature of the domino problem, two different primes need to be used).

Then, use the formula Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving to construct the Sudoku function Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, which There will be some kind of embedding. Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingwhere

is two different large prime numbers (for example, you can take Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving ), Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving represents the number of times Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving is divided by Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving, and Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

is the last non-zero digit in the

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving expansion of Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving: Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving(

,andTerence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving). Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingIn the case of

, the first component of (1) looks like this: Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingA typical example of the final component

looks like this: Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving

Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close pavingInteresting Yes, I don’t know why, but the decoration here basically follows the rules of the children’s game “Fizz Buzz”

The above is the detailed content of Terence Tao approaches another 60-year geometry problem! A new breakthrough has been made in the problem of periodic close paving. For more information, please follow other related articles on the PHP Chinese website!

Statement:
This article is reproduced at:51cto.com. If there is any infringement, please contact admin@php.cn delete