2015/10/20 by Rudi Mrazović, Mrazović, Rudi · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.1510.05998
openalex publication_date 2015/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A well-known conjecture in analytic number theory states that for every pair of sets X,Y⊂ℤ/pℤ, each of size at least log C p (for some constant C) we have that the number of pairs (x,y)∈ X× Y such that x+y is a quadratic residue modulo p differs from \frac12|X||Y| by o(|X||Y|). We address the probabilistic analogue of this question, that is for every fixed δ>0, given a finite group G and A⊂ G a random subset of density \frac12, we prove that with high probability for all subsets |X|,|Y|≥ log 2+δ |G|, the number of pairs (x,y)∈ X× Y such that xy∈ A differs from \frac12|X||Y| by o(|X||Y|).