Abstract
LetT(N) be the least integer such that one can assign ± 1’s to anyN points in the unit square so that the sum of these values in any rectangle with sides parallel to those of the square have absolute value at mostT(N). G. Tusnádi asked what could be said about the order of magnitude ofT(N). We prove
In contrast, ifT*(N) denotes the corresponding quantity where rectangles of any possible orientation are considered, we have
for anyε > 0.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Beck, Roth’s estimate of the discrepancy of integer sequences is nearly sharp,Combinatorica1(4) (1981), 319–325.
J. Beck andT. Fiala, “Integer-Making” theorems,Discrete Applied Math.3 (1981), 1–8.
P. Erdős andJ. Spencer,Probabilistic methods in combinatorics, Akadémiai Kiadó, Budapest, 1974.
J. H. Halton, On the efficiency of certain quasirandom sequences of points in evaluating multi-dimensional integrals,Num. Math.2 (1960), 84–90.
P. Major, On the invariance principle for sums of independent identically distributed random variables,Journal of Multivariate Analysis8 (1978), 487–517.
V. V. Petrov,Sums of independent random variables (in Russian), Moscow, Nauka, 1972 (see Ch. X, §1, Lemma 1).
K. F. Roth, On irregularities of distribution,Mathematika7 (1954), 73–79.
W. M. Schmidt, Irregularities of distribution IV.,Inv. Math.7 (1969), 55–82.
W. M. Schmidt, Irregularities of distribution VII.,Acta Arithmetica21 (1972), 45–50.
W. M. Schmidt,On irregularities of distribution, Tata Inst. of Fund. Res. Lectures on Math. and Phys.56 (1977).
J. G. van der Corput, Verteilungsfunktionen I.,Proc. Kon. Ned. Akad. v. Wetensch.38 (1935), 813–821.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Beck, J. Balanced two-colorings of finite sets in the square I. Combinatorica 1, 327–335 (1981). https://doi.org/10.1007/BF02579453
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02579453