On the complexity of families of pseudo-random subsets

DOI10.5802/AIF.2847zbMATH Open1314.11048arXiv1302.4622OpenAlexW2962769037MaRDI QIDQ486751FDOQ486751

Yong-Cai Geng, Sumit K. Garg

Publication date: 16 January 2015

Published in: Annales de l’institut Fourier (Search for Journal in Brave)

Abstract: In this paper we are interested in the following problem. Let $p$ be a prime number, $Ssubset{F}_p$ and $cPsubsetPin{F}_p[X]:degPled$. What is the largest integer $k$ such that for all subsets $cA,cB$ of $F_p$ satisfying $cAcapcB=emptyset$ and $|cAcupcB|=k$, there exists $PincP$ such that $P(x)inS$ if $xincA$ and $P(x)otinS$ if $xincB$? This problem corresponds to the study of the complexity of some families of pseudo-random subsets. First we recall this complexity definition and the context of pseudo-random subsets. Then we state the different results we have obtained according to the shape of the sets $S$ and $cP$ considered. Some proofs are based on upper bounds for exponential sums or characters sums in finite fields, other proofs use combinatorics and additive number theory.

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

Recommendations

• Various approaches for the study of the complexity of some families of pseudorandom subsets
• On large families of subsets of the set of the integers not exceeding \(N\)
• Large families of pseudorandom subsets formed by power residues
• On pseudorandom subsets in finite fields. I: Measure of pseudorandomness and support of Boolean functions
• Large family of pseudorandom subsets of the set of the integers not exceeding \(N\)

zbMATH Keywords

complexityexponential sumspseudo-random subsetscharacter sums

Mathematics Subject Classification ID

Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Estimates on exponential sums (11L07) Pseudo-random numbers; Monte Carlo methods (11K45)

Cites Work

• Number of Points of Varieties in Finite Fields
• La conjecture de Weil. I
• A complexity measure for families of binary sequences
• On finite pseudorandom binary sequences I: Measure of pseudorandomness, the Legendre symbol
• Title not available (Why is that?)
• On Exponential Sums in Finite Fields
• Exponential sums and Newton polyhedra: cohomology and estimates
• Equations over finite fields. An elementary approach
• On the Rationality of the Zeta Function of an Algebraic Variety
• Construction of pseudorandom binary sequences using additive characters
• On large families of subsets of the set of the integers not exceeding \(N\)
• A finite pseudorandom binary sequence
• Incomplete Kloosterman sums and a divisor problem. Appendix: On some exponential sums by Bryan J. Birch and Enrico Bombieri
• On the pseudo-randomness of subsets related to primitive roots
• Sum-free sets in abelian groups
• On pseudo-random subsets of the set of the integers not exceeding \(N\)
• Purity of exponential sums on 𝔸 n , II
• Large families of pseudorandom subsets formed by power residues
• Title not available (Why is that?)
• Bounds for exponential sums and their applications to pseudorandom numbers
• On \(p\)-pseudorandom binary sequences

Cited In (5)

• A new lower bound on the family complexity of Legendre sequences
• On the complexity of a family of Legendre sequences with irreducible polynomials
• On the pseudorandom properties of subsets constructed by using primitive roots
• On multi-dimensional pseudorandom subsets
• On pseudorandomness of families of binary sequences

This page was built for publication: On the complexity of families of pseudo-random subsets

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