Extractors in Paley graphs: a random model

DOI10.1016/J.EJC.2015.12.009MaRDI QIDQ5964262zbMATH OpenOpenAlexFDO

Authors Rudi Mrazović

Publication date 29 February 2016

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.05998

zbMATH Keywords

Paley graphs

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Random graphs (graph-theoretic aspects) (05C80) Graph theory (05C99) Other combinatorial number theory (11B75)

Abstract: A well-known conjecture in analytic number theory states that for every pair of sets $X,YsubsetmathbbZ/pmathbbZ$, each of size at least $lo{g}^{C}p$ (for some constant $C$) we have that the number of pairs $(x,y)inXimesY$ such that $x+y$ is a quadratic residue modulo $p$ differs from $frac12|X||Y|$ by $oleft(|X||Y|ight)$. We address the probabilistic analogue of this question, that is for every fixed $delta>0$, given a finite group $G$ and $AsubsetG$ a random subset of density $frac12$, we prove that with high probability for all subsets $|X|,|Y|geqlo{g}^{2+delta}|G|$, the number of pairs $(x,y)inXimesY$ such that $xyinA$ differs from $frac12|X||Y|$ by $oleft(|X||Y|ight)$.

Recommendations

• A random model for the Paley graph
• Refined estimates concerning sumsets contained in the roots of unity
• Arithmetic structures in random sets
• Counting sets with small sumset and applications
• Counting sets with small sumset, and the clique number of random Cayley graphs

Cites work

• A probabilistic technique for finding almost-periods of convolutions
• Can visibility graphs be represented compactly?
• Counting sets with small sumset, and the clique number of random Cayley graphs
• Extracting Randomness Using Few Independent Sources
• scientific article; zbMATH DE number 2121181 (Why is no real title available?)
• MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
• Probability Inequalities for Sums of Bounded Random Variables
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity

Cited in

(6)

• On subgraphs of random Cayley sum graphs
• A Cheeger type inequality in finite Cayley sum graphs
• A random model for the Paley graph
• On the subgraphs of Cayley sum graphs
• The VC-dimension of random subsets of finite groups
• Low-degree polynomials are good extractors

This page was built for publication: Extractors in Paley graphs: a random model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5964262)