×

Constructing small sets that are uniform in arithmetic progressions. (English) Zbl 0799.11022

Let \(\mathbb{Z}_ N\) be the set of residue classes \(\text{mod }N\). For \(A,S\subseteq \mathbb{Z}_ N\), the discrepancy of \(A\) in \(S\) is defined by \[ D_ A(S)= \biggl| {{| A\cap S|} \over {| A|}} - {{| S|} \over N}\biggr|, \] \(|\cdot|\) denoting the cardinality of a set. Similarly \(D_ A(S)\) can be defined for multisets. For a family \({\mathcal F}\) of subsets of \(\mathbb{Z}_ N\), let \(D_ A(F)= \max_{S\in{\mathcal F}} D_ A(S)\). The authors consider the family \({\mathcal J}_ N\) of all intervals of \(\mathbb{Z}_ N\). For \(\varepsilon>0\), \(A\subseteq \mathbb{Z}_ N\) is called \(\varepsilon\)-uniform \(\pmod N\) if for all \(x\in\mathbb{Z}^*_ N\), \(D_{xA} ({\mathcal J}_ N)\leq \varepsilon\), where \(xA= \{xa\): \(a\in A\}\). The authors give an explicit construction of sets \(A_{\varepsilon, N}\) that are \(\varepsilon\)-uniform \(\text{mod } N\) and satisfy \(| A_{\varepsilon, N}|\leq (\varepsilon^{-1} \log N)^{O(1)}\).
Reviewer: R.F.Tichy (Graz)

MSC:

11K06 General theory of distribution modulo \(1\)
11B25 Arithmetic progressions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF02579452 · Zbl 0491.10046 · doi:10.1007/BF02579452
[2] Alon, Random Structures and Algorithms
[3] DOI: 10.1112/blms/22.6.583 · Zbl 0733.11005 · doi:10.1112/blms/22.6.583
[4] Ajtai, Proc. 18th STOC pp 30– (1986)
[5] DOI: 10.1112/plms/s3-54.1.38 · Zbl 0609.10042 · doi:10.1112/plms/s3-54.1.38
[6] Beck, Irregularities of Distributions (1987)
[7] Roth, Ada Arith. 9 pp 257– (1964)
[8] Galil, Proc. 18th STOC pp 39– (1986)
[9] Even, Proc. 24th STOC pp 10– (1992)
[10] Chung, J. AMS 2 pp 187– (1989)
[11] Katz, J. AMS 2 pp 197– (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.