Monday, July 16, 2018

[mcwnlliy] On the width of a Gaussian Moat

TSUCHIMURA, Nobuyuki, "Computational Results for the Gaussian Moat Problem,"

Tsuchimura uses the term "width" in an unusual way, different from the popular meaning of "width".  To distinguish the two meanings where there might be ambiguity, we will write "technical width" for the sense used by Tsuchimura and we will write "popular width" to mean the meaning of "width" as popularly understood: the Euclidean distance (by the Pythagorean theorem) between two Gaussian primes on either side of the moat at its narrowest point (strait).

"Technical width" is synonymous with the step size k, in particular, the step size which failed to walk to infinity.  Therefore, when Tsuchimura establishes the existence of a moat of technical width sqrt(36)=6, it means that the algorithm walking outwards with a step size of 6 terminated; that is, it discovered a moat of popular width strictly greater than than 6, because step size 6 was not enough to cross it.  A step size of 6 gets you around the connected component inside the moat, but not across it.  The technical width of the moat is 6; the popular width is 6+delta.

Because of the discreteness of the Gaussian Moat Problem, we know (or have a very good guess) what that value of 6+delta is.  The next largest number after 6=sqrt(36) is sqrt(37).  However, because Gaussian primes (other than 1+i and its symmetries) all have the same checkerboard parity, the next largest possible distance between Gaussian primes is sqrt(40).  It could be that the popular width of the moat is even larger than sqrt(40), but that would be highly unlikely: whenever the step size is increased, the frontier increases dramatically.

The sequence of possible moat widths (squared) is OEIS A128106.  The popular width is one sequence element after the technical width.

To summarize, the result of Tsuchimura is that a moat of technical width 6, or a moat of popular width sqrt(40) separates the origin from infinity.  The current unsolved problem is whether a step size of sqrt(40) is sufficient to get to infinity (but the smart money is on "no", i.e., there exists a moat of technical width sqrt(40).).

The current Gaussian moat Wikipedia article includes an illustration of a moat with the caption explaining the moat has width 2.  This 2 is the popular width.  The same moat, with "Total size of the component" of 14, is listed as k=sqrt(2) in Tsuchimura's paper.

The previous paper,

Gethner, Wagon, and Wick, "A Stroll through the Gaussian Primes"

does not use the word width to mean technical width.  Instead, it refers to a moat with technical width X as an X-moat.  Incidentally, the paper illustrates that the connected component for various given step sizes have interesting shapes.

Incidentally, one cannot reach anywhere from the origin stepping only on Gaussian primes, because the origin, 0+0i, is itself not prime.

No comments :