Constructing Small Sets that are Uniform in Arithmetic Progressions

Alexander Razborov, Endre Szemerédi, Avi Wigderson

Type: Article

Publication Date: 1993-12-01

Citations: 35

DOI: https://doi.org/10.1017/s0963548300000870

View Publication

Locations

Combinatorics Probability Computing - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	A uniform set with fewer than expected arithmetic progressions of length 4	2020	W. T. Gowers
+ PDF Chat	Residue classes containing an unexpected number of primes	2012	Daniel Fiorilli
+	modulo-n arithmetic	2011
+	modulo-n arithmetic	2000	Martin H. Weik
+	Density of non-residues in short intervals	2006	William D. Banks M. Z. Garaev D. R. Heath‐Brown Igor E. Shparlinski
+	Distribution of factorials modulo p	2015	Oleksiy Klurman Marc Munsch
+	Distribution of factorials modulo p	2015	Oleksiy Klurman Marc Munsch
+	An Indexing for Quadratic Residues Modulo $N$ and a Non-uniform Efficient Decoding Algorithm	2018	Nicollas M. Sdroievski Murilo V. G. da Silva André L. Vignatti
+	Approximate arithmetic structure in large sets of integers	2019	Jonathan M. Fraser Yu Han
+	Detection of Primes in the Set of Residues of Divisors of a Given Number	2018	Rafał Bystrzycki
+	Narrow arithmetic progressions in the primes	2015	Xuancheng Shao
+	Minimizing the frequency of carries in modular addition	2015	Francesco Monopoli
+	On the Uniform Distribution in Residue Classes of Dense Sets of Integers with Distinct Sums	1999	Mihail N. Kolountzakis
+	On the Value Set of n! Modulo a Prime	2005	William D. Banks
+ PDF Chat	Approximate arithmetic structure in large sets of integers	2021	Jonathan M. Fraser Han Yu
+	The residues modulo m of products of random integers	1999	Yuliy Baryshnikov Wolfgang Stadje
+	An Indexing for Quadratic Residues Modulo $N$ and a Non-uniform Efficient Decoding Algorithm	2018	Nicollas M. Sdroievski Murilo V. G. da Silva André L. Vignatti
+	On the sequence $n! \bmod p$	2023	Alexandr Grebennikov Арсений Сагдеев Aliaksei Semchankau Aliaksei Vasilevskii
+	Sparse variance for $$k$$ k -free numbers in arithmetic progressions	2014	Fabian Dehnert
+ PDF Chat	Narrow Arithmetic Progressions in the Primes	2016	Xuancheng Shao

Works That Cite This (14)

Action	Title	Year	Authors
+	Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions.	2010	Adi Akavia
+ PDF Chat	Explicit constructions of RIP matrices and related problems	2011	Jean Bourgain S. J. Dilworth Kevin Ford Sergeĭ Konyagin Denka Kutzarova
+	Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions	2013	Adi Akavia
+	ϵ-discrepancy sets and their application for interpolation of sparse polynomials	1995	Noga Alon Yishay Mansour
+	Explicit small sets with ε-discrepancy on Bohr sets	2014	Adi Akavia
+	The Discrepancy Method	1998	Bernard Chazelle
+	Near-Optimal Cayley Expanders for Abelian Groups	2021	Akhil Jalan Dana Moshkovitz
+	Quantum Hashing via Classical $ε$-universal Hashing Constructions	2014	Farid Ablayev Marat Ablayev
+	Improved constructions of quantum automata	2009	Andris Ambainis Nikolajs Nahimovs
+	Improved constructions of quantum automata	2008	Andris Ambainis Nikolajs Nahimovs

Works Cited by This (8)

Action	Title	Year	Authors
+	Irregularities of Distribution	1987	József Beck William Chen
+	Roth’s estimate of the discrepancy of integer sequences is nearly sharp	1981	József Beck
+ PDF Chat	An estimate for character sums	1989	Nicholas M. Katz
+	Random Cayley graphs and expanders	1994	Noga Alon Yuval Roichman
+	Construction of a Thin Set with small Fourier Coefficients	1990	Miklós Ajtai Henryk Iwaniec János Komlós J. Pintz Endre Szemerédi
+	Approximations of general independent distributions	1992	Guy Even Oded Goldreich Michael Luby Noam Nisan Boban Veličković
+ PDF Chat	Diameters and eigenvalues	1989	Fan Chung
+	Essential Components	1987	Imre Z. Ruzsa