OctoInformBeta

Uniformly bounded components of Gaussian-prime graphs

A Gaussian prime is an irreducible element of the ring ℤ[i]\mathbb{Z}[i] of Gaussian integers. For a real number DD, let GDG_D be the graph whose vertices are all the Gaussian primes, with an edge between distinct primes zz and ww whenever |z−w|≤D|z-w|\le D. The Gaussian moat problem asks whether some GDG_D contains an infinite path with no repeated vertex. The Gaussian moat conjecture asserts that no GDG_D does.

Gethner and Stark trace the question to Basil Gordon at the 1962 International Congress of Mathematicians in Stockholm. Erdős later credited the problem to Gordon and Motzkin. Gethner, Wagon and Wick constructed large disks free of Gaussian primes with centers on any line through two Gaussian integers. They also constructed arbitrarily isolated Gaussian primes on the real axis, crediting Vardi with an independent proof. Tsuchimura obtained by computation a finite bound on the distance reachable from the origin through Gaussian primes in steps of length at most 66. Gethner and Stark formulated a bound on the length of a walk through distinct Gaussian primes that is uniform in its starting point. They proposed sieving by small Gaussian primes for step bounds larger than 22. Vardi studied the passage from the absence of an infinite path to a uniform bound on the sizes of the connected components of GDG_D.

The preprint proves the uniform component bound: for every real DD there is a finite BDB_D such that every connected component of GDG_D has at most BDB_D vertices, components through primes on the coordinate axes included. Consequently every sequence of distinct Gaussian primes whose successive distances are at most DD has at most BDB_D terms. This proves the Gaussian moat conjecture. The bound BDB_D is not explicit. For a rational prime p≡1(mod⁡4)p\equiv1\pmod{4}, let πp\pi_p and πp¯\overline{\pi_p} be its two conjugate Gaussian prime factors, each of norm pp. For a finite set 𝒫\mathcal{P} of such primes, let 𝒜(𝒫)\mathcal{A}(\mathcal{P}) be the set of Gaussian integers divisible by none of πp,πp¯\pi_p,\overline{\pi_p} with p∈𝒫p\in\mathcal{P}. The preprint also proves the finite sieve obstruction: for every D≥1D\ge1 there is a finite set 𝒫D\mathcal{P}_D of rational primes p≡1(mod⁡4)p\equiv1\pmod{4} such that 𝒜(𝒫D)\mathcal{A}(\mathcal{P}_D) contains no infinite sequence of distinct points whose successive distances are at most DD.

The Lean library GaussianMoat proves the uniform component bound. It also proves the finite sieve obstruction. It takes no result as a hypothesis. Lean has checked every result of the Lean library, so the Lean library is the reference: each result on these pages is the Lean library’s, stated as the Lean library states it and linked to the Lean declaration behind it. Where the preprint states a result differently, the page gives the Lean library’s statement, with the preprint’s beside it. The preprint is a guide only, which gives the results their order and their names. In place of the prime number theorem in arithmetic progressions, on which the preprint draws, the Lean library proves that there are c,δ>0c,\delta>0 such that for every large XX at least cXcX integers jj with X≤jlog⁡2≤1.05XX\le j\log 2\le 1.05X have at least δ2j/log⁡2j+1\delta 2^j/\log 2^{j+1} primes p≡1(mod⁡4)p\equiv1\pmod{4} in [2j,2j+1)[2^j,2^{j+1}).

The Lean library: GaussianMoat

GaussianMoat is a Lean library: 25 items, in eight groups. Each has a page written by OctoInform, listed below.

§1. The Gaussian moat problem 4 items
  1. Gaussian primes and the graph G_D The graph joining Gaussian primes at bounded distance.
  2. Theorem 1.1 Self-avoiding Gaussian prime walks with bounded steps are uniformly short.
  3. The sieved set A(𝒫) Sieving by split primes leaves a periodic set.
  4. Theorem 1.2 Finite sieves block self-avoiding walks with steps at most D≥1D \ge 1.
§2. Periodicity and the uniform bound 1 item
  1. Proposition 2.1 Sieves without self-avoiding walks bound the Gaussian prime components.
§3. Arithmetic, walks, and entropy 5 items
  1. Dyadic batches of split primes Dyadic batches of split primes, many of them large.
  2. Finite laws, entropy and information Entropy and mutual information on finite probability spaces.
  3. Lemma 3.1 Displacements of a walk over bounded lags have bounded entropy.
  4. Lemma 3.2 Entropy gaps between random variables that rarely differ.
  5. Lemma 3.3 A short list of candidates bounds conditional entropy.
§4. Entropy enrichment from a forward segment 4 items
  1. Signed subsets, f_Z, and the difference transition Signed residue entropy and the difference transition of a walk.
  2. Lemma 4.1 Differences of a walk segment bound the area it spans.
  3. Lemma 4.2 Random signed products rarely divide nonzero points of thin rectangles.
  4. Lemma 4.3 Residue entropy enrichment by a difference transition.
§5. Coverage from shared continuation data 3 items
  1. Signed coordinates and (τ, β) coverage Residues modulo signed factors and low residues of laws.
  2. Lemma 5.1 Conditioning on data of small entropy costs signed residues little.
  3. Theorem 5.2 Coverage passes one step back through shared continuation data.
§6. A common sampling schedule 3 items
  1. The schedule, checkpoints and the terminal time t* Random sampling times from difference transitions and a uniform offset.
  2. Lemma 6.1 Shift bounds and smoothing for the common sampling schedule.
  3. Proposition 6.2 Few low residues at the terminal time for most signed primes.
§7. Zero avoidance costs information 3 items
  1. Increment words and their lengths Increment words sum to the displacement over their window.
  2. Residues modulo a finite set of Gaussian integers Residues modulo nonzero moduli have entropy at most their weight.
  3. Proposition 7.1 Avoiding a certified batch costs information.
§8. The common-law entropy budget 2 items
  1. Lemma 8.1 A telescoping bound on residue information along a walk.
  2. Proof of Theorem 1.2 Sieve certificates on dyadic batches and the walks they exclude.

No item matches.