Discrepancy of sums of three arithmetic progressions (Q813920): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q587322
Property / reviewed by
 
Property / reviewed by: Štefan Porubský / rank
Normal rank
 

Revision as of 17:43, 19 February 2024

scientific article
Language Label Description Also known as
English
Discrepancy of sums of three arithmetic progressions
scientific article

    Statements

    Discrepancy of sums of three arithmetic progressions (English)
    0 references
    31 January 2006
    0 references
    Let \((X,{\mathcal F})\) be a set system on a finite set. The author proves that for the (worst-case) discrepancy \(\text{disc}({\mathcal F})=\min_{\chi:X\to\{-1,1\}}\max_{S\in{\mathcal F}}\left| \sum_{x\in S}\chi(x)\right| \) of the set system \({\mathcal F}\) formed by all sums of three arithmetic progressions on \(X=\{0,1,2,\dots,n\}\) we have \(\text{disc}({\mathcal F})=\Omega(n^{1/2})\).
    0 references
    discrepancy
    0 references
    arithmetic progression
    0 references
    circulant matrix
    0 references

    Identifiers