On Linnik's Conjecture: Sums of Squares and Microsquares

We show that almost all natural numbers n not divisible by 4, and not congruent to 7 modulo 8, are represented as the sum of three squares, one of which is the square of an integer no larger than (log n)(1+epsilon). This answers a conjecture of Linnik for almost all natural numbers, and sharpens a conclusion of Bourgain, Rudnick, and Sarnak concerning nearest neighbor distances between normalized integral points on the sphere.