Counting Rainbow Solutions of a Linear Equation over Fp via Fourier-Analytic Methods

Abstract

We study rainbow solutions to linear equations modulo a prime p, where the residue classes are partitioned into n color classes. Using the Fourier method, we derive a universal lower bound that depends only on the class densities and a single spectral parameter: the Fourier bias (the largest nontrivial Fourier coefficient) of each class. When the biases are at the square-root cancellation scale 𝑝−1/2 (for random colorings, up to a log𝑝−−−−−√ factor), the bound recovers the optimal growth 𝑝𝑛−1 with an explicit leading constant and negligible error. Our results complement recent work: in low-bias regimes (pseudorandom or random) they yield sharper quantitative bounds with transparent constants, and the bound requires no extra hypotheses such as coefficient separability.