Discrepancy

../

E0067/: Asks whether every function on the naturals taking values plus and minus one has unbounded discrepancy: for every bound, some step and length give a partial sum along the multiples of the step that exceeds it.

E0161/: Asks whether the smallest size forcing balanced two-colorings of a complete uniform hypergraph varies continuously with the density parameter or jumps.

E0162/: Asks whether the size threshold beyond which some two-coloring of K_n balances every large induced subgraph grows like c log n; corrected to "smallest", it is the question of Problem 563, which is open.

E0176/: Bounds the least N forcing every plus-minus-one sign pattern to have a k-term arithmetic progression with partial sum of absolute value at least a given size.

E0177/: The smallest bound, as a function of the common difference, on the largest partial sum along arithmetic progressions of a single plus-minus-one sign function.

E0178/: Asks whether one plus-minus-one function can keep the initial partial sums along each of infinitely many prescribed integer sequences bounded.

E0255/: Asks whether every infinite sequence in the unit interval has some subinterval whose counting discrepancy is unbounded.

E0987/: Concerns the limiting sizes of the exponential sums of an infinite sequence in the unit interval taken at integer frequencies.

E0988/: Concerns how small the spherical cap discrepancy of a finite set of points on the unit sphere can be made.

E0989/: Concerns how slowly the discrepancy of an infinite plane sequence, measured against circles of radius r and their area, can grow.

E0991/: Concerns the distribution of the point sets on the unit sphere that maximize the product of all pairwise distances.

E0992/: Asks whether, for any increasing integer sequence, the discrepancy of its multiples of alpha stays near the square root of N for almost every alpha.

E0994/: Asks whether, for almost every alpha, the fractional parts of its integer multiples visit every measurable set in the unit interval with frequency its measure.

E0995/: Estimates the growth of the sums of a square integrable function at the fractional parts of alpha times a lacunary integer sequence, for almost every alpha.

E0997/: Asks whether the fractional parts of alpha times the primes fail to be well distributed for every alpha.

E1028/: Estimates the least possible maximum, over subsets of the first n integers, of the sum of a plus or minus one valued function over the pairs inside that subset.

---

The Erdos discrepancy problem and its relatives: how unbalanced a plus/minus one coloring must become along arithmetic progressions, dilates and set systems, and irregularities of distribution of sequences and of graph colorings.

Site tags routed here: additive combinatorics, analysis, arithmetic progressions, combinatorics, discrepancy, graph theory, hypergraphs, primes, ramsey theory.