Gauss Sum Walks
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This Demonstration shows two types of pseudorandom walks constructed from Gauss sums, an exponential (red) and a quadratic residue (blue) Gauss walk. The random walk starts at the origin, takes steps given by the terms of the exponential or quadratic residue Gauss sum modulo 
, and ends at the value of the Gauss sum. By a famous result of Gauss, if the modulus 
is a prime number, the two walks always end at the same point, located at 
or 
depending on the remainder of 
modulo 4. The exponential Gauss walk has a characteristic shape consisting of two spirals. The quadratic residue Gauss walk exhibits a more complex behavior whose shape is roughly determined by the remainder of 
modulo 24.
Contributed by: Erqian Wang (June 2020)
(Based on an undergraduate research project at the Illinois Geometry Lab by Ka Fung Tjin, Erqian Wang and Yifan Zhang and directed by A. J. Hildebrand.)
Open content licensed under CC BY-NC-SA
Snapshots
Details
Given an integer 
, the exponential sum version of the Gauss sum modulo 
is defined by
and the quadratic residue version is defined by
,
where 
is the Jacobi symbol, which has values 0, 1, 
depending on the quadratic residue properties of 
modulo 
.
A famous result of Gauss states that when the modulus 
is a prime 
, the two sums 
and 
have the same value 
, given by
.
For composite moduli 
, the two sums are in general different, and the above formula does not necessarily hold.
It was shown by Lehmer [1] that the exponential Gauss walk always has the spiral-type shape observed in the visualization. On the other hand, the shape of the quadratic residue Gauss walk is more mysterious and has not been explored in the literature.
Reference
[1] D. H. Lehmer, "Incomplete Gauss Sums," Mathematika, 23(2), 1976 pp. 125–135. doi:10.1112/S0025579300008718.
Permanent Citation
Random Walk Solutions to the Dirichlet Problem for the Laplace Equation
Cameron Nachreiner
Four Hypergeometric Lattice Walks
Brad Klee
Coupon Collector Problem
Ed Pegg Jr
Pseudorandom Walks with Generalized Gauss Sums
Ka Fung Tjin
Partial Sums of a Lambert Series
Enrique Zeleny
Real Number Walks versus Algorithmic Random Walks
Khoa Tran and Laila Zhexembay
Random Walks and the Heat Equation
Yirui Luo
Gauss Map
Enrique Zeleny
The Variance Gamma Process
Andrzej Kozlowski
Option Prices in the Variance Gamma Model
Andrzej Kozlowski