Infinite Moduli, Roots of Unity, and the Density of Coprime Channels

Visibility and Lattice Geometry

For any lattice point (a,b) ∈ ℤ², we define the visibility indicator:

A lattice point (a,b) is visible from the origin if and only if gcd(a,b) = 1. These primitive lattice vectors determine rays from the origin that hit no other lattice point before reaching (a,b). The set of primitive directions forms a fundamental geometric object in number theory.

Key Insight: The angle θ = arctan(b/a) for a primitive vector (a,b) provides a one-to-one correspondence between primitive lattice directions and angles that can be expressed as rational multiples of π (modulo appropriate symmetries).

Gaussian Integers and Norm Structure

Every primitive lattice vector (a,b) corresponds to a Gaussian integer z = a + bi with the property that gcd(a,b) = 1. The norm of this Gaussian integer is:

This norm connects lattice geometry to the theory of sums of two squares. A positive integer n can be expressed as a sum of two coprime squares (with specific multiplicity) if and only if in the prime factorization of n, every prime p ≡ 3 (mod 4) appears to an even power.

Fermat's Two-Square Theorem: A prime p can be expressed as p = a² + b² if and only if p = 2 or p ≡ 1 (mod 4). Moreover, this representation is unique up to signs and order when gcd(a,b) = 1.

The Riemann Zeta Function Connection

The constant 6/π² appears throughout number theory and is intimately connected to the Riemann zeta function ζ(s). Euler famously proved in 1734 that:

Therefore, our density constant is simply 6/π² = 1/ζ(2). This connection reveals that the probability two random integers are coprime is the reciprocal of ζ(2).

Historical Development

Leonhard Euler (1707-1783) first proved the Basel problem and established the product formula for the zeta function:

This product over primes directly implies the coprime density result. The probability that a prime p divides both random integers a and b is 1/p². Thus the probability that p divides neither (or only one) is 1 - 1/p². Taking the product over all primes:

P(gcd(a,b) = 1) = Π_p (1 - 1/p²) = 1/ζ(2) = 6/π²

Modular Embedding and Circle Geometry

Each reduced residue r with gcd(r,m) = 1 maps naturally to the unit circle via the modular embedding:

This embedding preserves the multiplicative structure of (ℤ/mℤ)* and provides a geometric representation of the reduced residue system. The φ(m) points form a regular φ(m)-gon inscribed in the unit circle, though not necessarily with consecutive vertices.

Proof Sketch: Average of φ(m)/m

We want to show that (1/N) Σ_m=1^N φ(m)/m → 6/π² as N → ∞.

Key insight: For each pair (a, b) with 1 ≤ a < b ≤ N, the pair contributes to φ(m) exactly when m is a common divisor of a and b, and gcd(a/m, b/m) = 1.

By Möbius inversion and manipulating the double sum:

Therefore the average converges to 6/π².

Connection to Farey Sequences

The Farey sequence F_n is the sequence of completely reduced fractions between 0 and 1 with denominators ≤ n, arranged in increasing order. For example:

The length of F_n is |F_n| = 1 + Σ_m=1ⁿ φ(m), which grows as (3/π²)n² + O(n log n). This is equivalent to our density theorem since we're counting coprime pairs (numerator, denominator).

Geometric Interpretation: Each element p/q ∈ F_n with gcd(p,q) = 1 corresponds to a primitive lattice direction (p,q) visible from the origin. The Farey sequence thus provides a canonical ordering of these visible directions within a bounded region.

Why Primes Don't Dominate

Although φ(p)/p = (p-1)/p → 1 for prime p, primes have density zero among integers by the Prime Number Theorem:

As x → ∞, the ratio π(x)/x → 0, so primes become increasingly sparse. Meanwhile, highly composite numbers (with many small prime factors) have small φ(m)/m ratios and dominate the average. For instance:

• φ(2)/2 = 1/2
• φ(6)/6 = 2/6 = 1/3 (divisible by 2 and 3)
• φ(30)/30 = 8/30 = 4/15 ≈ 0.267 (divisible by 2, 3, and 5)
• φ(210)/210 = 48/210 = 8/35 ≈ 0.229 (divisible by 2, 3, 5, and 7)

The global average balances these competing effects, converging to 6/π² ≈ 0.6079.

Lattice Point Counting and Primitive Vectors

The number of primitive lattice vectors (a,b) with a² + b² ≤ R² grows asymptotically as:

This provides a geometric interpretation of the coprime density: in a large circle of radius R, approximately 6/π of the area contains primitive lattice points.

Related Results

Dirichlet's theorem on primes in arithmetic progressions (1837) and the study of L-functions extend these density results to restricted sets of integers, providing a rich framework for understanding coprimality in various contexts.

Lattice-Based Cryptography: The hardness of finding short primitive vectors in high-dimensional lattices forms the basis of post-quantum cryptographic systems, connecting these classical results to modern applications.

For each modulus m, the reduced residue system Φ(m) = {r : gcd(r, m) = 1, 0 ≤ r < m} maps to points on the unit circle via r → exp(2πi r/m). The visualization below shows these points for varying moduli.

A lattice point (a, b) ∈ ℤ² is primitive (or visible from the origin) if gcd(a, b) = 1. These points correspond to Gaussian integers z = a + bi with norm N(z) = a² + b². The norm is prime when it equals 2 or a prime p ≡ 1 (mod 4), by Fermat's Two-Square Theorem.

Let A_N = #{(a, b) : 1 ≤ a, b ≤ N, gcd(a, b) = 1} be the count of coprime pairs in an N × N grid.

For each modulus m, the ratio φ(m)/m represents the fraction of residues coprime to m. The average of these ratios converges to the same constant 6/π².

This chart shows how the running average of φ(m)/m converges to 6/π² as we increase the maximum modulus. The horizontal line represents the theoretical limit.