Erdős discrepancy problem
E554302
The Erdős discrepancy problem is a famous question in combinatorial number theory that asks whether every infinite ±1 sequence has arbitrarily large discrepancy along some homogeneous arithmetic progression.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Erdős discrepancy problem canonical | 1 |
Statements (45)
| Predicate | Object |
|---|---|
| instanceOf |
mathematical problem
ⓘ
open problem in mathematics ⓘ |
| asksAbout |
discrepancy of ±1 sequences
ⓘ
homogeneous arithmetic progressions ⓘ |
| concerns | unboundedness of certain partial sums ⓘ |
| coreQuestion | whether every infinite ±1 sequence has unbounded discrepancy on some homogeneous arithmetic progression ⓘ |
| difficulty | hard ⓘ |
| difficultyClassification | very difficult problem in combinatorial number theory ⓘ |
| equivalentFormulation | for every ±1 sequence (x_n) and every C > 0 there exist n,d with |x_d + x_{2d} + … + x_{nd}| > C ⓘ |
| field |
combinatorial number theory
ⓘ
discrepancy theory ⓘ |
| formulation | for every function f: ℕ → {−1, +1} and every C > 0 there exist n,d ∈ ℕ such that |∑_{k=1}^{n} f(kd)| > C ⓘ |
| hasConsequence | every infinite ±1 sequence has arbitrarily large discrepancy along some homogeneous arithmetic progression ⓘ |
| hasOnlinePolymathProject | Polymath5 NERFINISHED ⓘ |
| hasVariant | Erdős discrepancy problem for completely multiplicative functions NERFINISHED ⓘ |
| implies | no infinite ±1 sequence has bounded discrepancy on all homogeneous arithmetic progressions ⓘ |
| influencedBy | classical problems of Erdős in additive and combinatorial number theory ⓘ |
| involvesQuantifiers | for all C > 0 there exist n,d ∈ ℕ ⓘ |
| motivation | understanding irregularities of distribution in sequences ⓘ |
| namedAfter | Paul Erdős NERFINISHED ⓘ |
| proposedBy | Paul Erdős NERFINISHED ⓘ |
| publication | Terence Tao’s 2016 paper in Journal d’Analyse Mathématique NERFINISHED ⓘ |
| quantifiesOver |
all infinite ±1 sequences
ⓘ
all positive integers C ⓘ positive integers d ⓘ positive integers n ⓘ |
| relatedTo |
Erdős–Turán conjecture
NERFINISHED
ⓘ
completely multiplicative functions ⓘ discrepancy of sequences ⓘ multiplicative functions ⓘ |
| solutionMethod |
Fourier analysis
ⓘ
analytic number theory ⓘ entropy decrement argument ⓘ probabilistic methods ⓘ |
| solvedBy | Terence Tao NERFINISHED ⓘ |
| status | solved ⓘ |
| studiedIn | Polymath5 project NERFINISHED ⓘ |
| topic |
arithmetic progressions
ⓘ
infinite sequences ⓘ partial sums ⓘ |
| usesConcept |
discrepancy
ⓘ
homogeneous arithmetic progression ⓘ ±1 sequence ⓘ |
| yearProposed | 1930s ⓘ |
| yearSolved | 2015 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.