Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-25T00:54:02.206Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructing Small Sets that are Uniform in Arithmetic Progressions

Published online by Cambridge University Press:  12 September 2008

A. Razborov ,
E. Szemerédi  and
A. Wigderson
A. Razborov
Affiliation:
Steklov Mathematical Institute, Moscow, Russia
E. Szemerédi
Affiliation:
Rutgers University, New Brunswick N. J., USA
A. Wigderson
Affiliation:
Hebrew University, Jerusalem, Israel
Get access Rights & Permissions [Opens in a new window]

Abstract

For every integer N, we explicitly construct a subset of residues mod N of size(log N)o(1) which is nearly uniformly distributed in every arithmetic progression modulo N.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 4 , December 1993 , pp. 513 - 518
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Ajtai, M., Babai, L., Komlós, J., Pudlák, P., Rödl, V., Szeméredi, E. and Turán, G. (1986) Two lower bounds for branching programs. Proc. 18th STOC 30–38.Google Scholar
[2]Ajtai, M., Iwaniec, H., Komlós, J., Pintz, J. and Szemerédi, E. (1990) Construction of a thin set with small Fourier coefficients. Bull. London Math. Soc. 22 583–590.CrossRefGoogle Scholar
[3]Alon, N. and Roichman, Y. (in press) Random Cayley graphs and expanders. Random Structures and Algorithms.Google Scholar
[4]Beck, J. (1981) Roth's estimate of discrepancy of integer sequences is nearly sharp. Combinatorica 1 319–325.Google Scholar
[5]Beck, J. and Chen, W. (1987) Irregularities of Distributions, Cambridge University Press.CrossRefGoogle Scholar
[6]Chung, F. R. K. (1989) Diameters and eigenvalues. J. AMS 2 187–196.Google Scholar
[7]Even, G., Goldreich, O., Luby, M., Nisan, N. and Veličković, B. (1992) Approximations of general independent distributions. Proc. 24th STOC 10–16.Google Scholar
[8]Galil, Z., Kannan, R. and Szemerédi, E. (1986) On nontrivial separators for k-page graphs, and simulations by nondeterministic one-tape Turing machines. Proc. 18th STOC 39–49.Google Scholar
[9]Katz, N. M. (1989) An estimate for character sums. J. AMS 2 197–200.Google Scholar
[10]Roth, K. F. (1964) Remark concerning integer sequences. Ada Arith. 9 257–260.CrossRefGoogle Scholar
[11]Ruzsa, I. (1987) Essential components. Proc. London Math. Soc. 54 38–56.Google Scholar