Results on walks through Gaussian primes and their assumptions

The course proves the statements below; each link leads to the statement with its assumptions and its proof. The lessons are self-checked by the writing AI; independent mathematical review is not complete.

• Uniform component bound — Theorem 1.1. Every real step bound D: all connected components of the graph joining Gaussian primes at distance at most D have at most B_D vertices; no infinite walk through distinct Gaussian primes has steps at most D.
• Residues modulo a split prime — Proposition 2.4. Gaussian primes of norm p = 1 mod 4: the residue field has p elements and is represented by integers; nonzero multiples have length at least sqrt(p); divisibility by both conjugate factors means divisibility by p.
• Periodic reduction — Theorem 4.1. D >= 1 and a finite set P of primes 1 mod 4 whose sieve set A(P) contains no infinite D-walk: every component of the Gaussian-prime graph has at most |E| + (K_D - 1)|E|Q^2 vertices, Q the product of P.
• Size of a batch — Proposition 5.1. Primes 1 mod 4 in [T, 2T]: their number is (1/2 + o(1)) T/log T, and k_T log(2T) <= (8 log 2) T for T >= 2.
• Pinsker's inequality — Theorem 5.3. Probability laws on a finite set: relative entropy (natural logarithms) is at least twice the squared total variation distance.
• Continuity of conditional entropy — Corollary 5.6. Pairs of finite variables on a product set of at most a elements with total variation at most e <= 1/2: conditional entropies differ by at most 2h(e) + 2e log a.
• Short lists — Lemma 6.1. Finite variables X (at most a values) and Y, lists L(y): log a - H(X|Y) >= rho log(a/b) - h(rho), where rho is the probability that X is on a list of size at most b.
• Concavity over random coordinates — Proposition 7.2. Exchangeable random index sequences independent of a finite variable Y: the average joint entropy of the first s coordinates is concave in s.
• One shared conditioning cost — Proposition 7.3. Index sequences with uniform marginals: high average joint entropy and a cheap shared conditioning variable give small average conditional deficit per coordinate, with no independence assumption.
• Hoeffding's inequality — Theorem 2.2. Independent real variables with values in [a_j, b_j]: P(S - ES >= t) <= exp(-2t^2 / sum (b_j - a_j)^2).
• Binomial lower tail — Proposition 3.1. Binomial law with n trials and success probability lambda, 0 < v < 1: P(B <= (1-v) n lambda) <= exp(-n lambda v^2 / 2).
• Edge isoperimetry of the cube — Theorem 4.1. Nonempty sets S of vertices of {0,1}^r: at least |S| log2(2^r/|S|) edges leave S.
• Many differences — Theorem 2.2. Stretches of n steps of a D-walk, A = diameter times width: (pi/24) n <= A <= D^2 n^2 and at least A/(pi D^2) distinct differences; the proof uses Brouwer's fixed-point theorem.
• Signed products avoid thin rectangles — Theorem 3.1. Distinct primes 1 mod 4 in [T, 2T], T >= 5, 0 < d < 1/4, d^3 r >= 2, centred rectangles with R W <= P^(1-d): a random product of conjugate factors has a nonzero multiple in the rectangle with probability at most exp(-d^3 r/(640 log 2)).
• Entropy enrichment — Theorem 3.1. Any D-walk, a batch of primes in [T, 2T], g^5 U >= K_D log T, q <= k: sampling an endpoint of a uniformly random distinct difference of the next exp(gU) steps halves the residue entropy deficit up to 16g.
• Coverage transfer — Theorem 3.1. Finite abelian residue groups of orders in [T, 2T] on a lattice: coverage of all continuation laws at a later checkpoint, nearly maximal joint entropy and a cheap shared vector of continuations give coverage with a larger exponent at the earlier checkpoint.
• Terminal coverage — Proposition 6.1. The common sampling schedule, any D-walk, large M: from every exact start at every checkpoint, the final residues have coverage for all but a small fraction of the signed coordinates of each batch.
• Information cost of a batch — Proposition 2.1. D-walks avoiding both zero classes of every sieving prime: each batch near T forces at least c_1/log T units of conditional information per increment at the common final time.
• Finite sieve obstruction — Theorem 4.1. Every D >= 1: a finite set of primes 1 mod 4 whose sieve set contains no infinite D-walk.

Reading order

Read the first lesson for the problem, the arithmetic of split primes and the reduction to a finite periodic sieve. The next two lessons collect the entropy and concentration tools; the fourth proves the geometric facts about walk stretches and signed products. The fifth and sixth lessons prove the enrichment and coverage-transfer principles, the seventh assembles them along one sampling schedule, and the last proves the finite sieve theorem and with it the uniform component bound.