Naslov
Extractors in Paley graphs : a random model

Autori
Mrazović, Rudi

Izvornik
Euoropean journal of combinatorics (0195-6698) 54 (2016); 154-162

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Payley graphs ; randomness extractors

Sažetak
A well-known conjecture in analytic number theory states that for every pair of sets $X, Y\subset\mathbb{; ; ; ; Z}; ; ; ; /p\mathbb{; ; ; ; Z}; ; ; ; $, each of size at least $\log ^C p$ (for some constant $C$) we have that for $(\frac12+o(1))|X||Y|$ of the pairs $(x, y)\in X\times Y$, $x+y$ is a quadratic residue modulo $p$. We address the probabilistic analogue of this question, that is for every fixed $\delta>0$, given a finite group $G$ and $A\subset G$ a random subset of density $\frac12$, we prove that with high probability for all subsets $|X|, |Y|\geq \log ^{; ; ; ; 2+\delta}; ; ; ; |G|$ for $(\frac12+o(1))|X||Y|$ of the pairs $(x, y)\in X\times Y$ we have $xy\in A$.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA