The Erdös discrepancy problem

DOI10.19086/DA.609MaRDI QIDQ2826233zbMATH OpenOpenAlexWikidataFDO

Authors Terence Tao

Publication date 10 October 2016

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1509.05363

zbMATH Keywords

completely multiplicative functionsDirichlet charactersdiscrepancyElliott conjectureErdős discrepancy problem

Mathematics Subject Classification ID

Irregularities of distribution, discrepancy (11K38) Arithmetic functions in probabilistic number theory (11K65)

Abstract: We show that for any sequence $$ taking values in $-1,+1$, the discrepancy ${\displaystyle }$ sup_{n,d in {�f N}} left|sum_{j=1}^n f(jd) ight| ${\displaystyle }$ of $f$ is infinite. This answers a question of ErdH{o}s. In fact the argument also applies to sequences $f$ taking values in the unit sphere of a real or complex Hilbert space. The argument uses three ingredients. The first is a Fourier-analytic reduction, obtained as part of the Polymath5 project on this problem, which reduces the problem to the case when $f$ is replaced by a (stochastic) completely multiplicative function $$. The second is a logarithmically averaged version of the Elliott conjecture, established recently by the author, which effectively reduces to the case when $$ usually pretends to be a modulated Dirichlet character. The final ingredient is (an extension of) a further argument obtained by the Polymath5 project which shows unbounded discrepancy in this case.

Review text

The main result in this paper is the following. Let \(H\) be a real or complex Hilbert space with norm \(\| \cdot \|_{H}\), and let \(f\) be a function defined on the positive integers \(\mathbb{N}\) such that \(\| f(n) \|_{H}=1\) for every \(n\in\mathbb{N}\). Then the discrepancy of \(f\), defined as NEWLINE\[CARRIAGE_RETURNNEWLINE\sup_{n,d\in\mathbb{N}}\left\| \sum_{j=1}^n f(jd) \right\|_{H},CARRIAGE_RETURNNEWLINE\]NEWLINE is infinite. As a special case, if \(f\) is a function taking values in \(\{-1,+1\}\), this result is the answer to an open question originally posed by Erdős, therefore known as the Erdős discrepancy problem.NEWLINENEWLINEThe proof of this theorem is based on a logarithmically averaged version of the Elliott conjecture, also recently shown by the author of this paper, and results obtained in the so-called \texttt{Polymath5} project.

Recommendations

• On the Erdős discrepancy problem
• The Erdős-Szekeres Problem
• About Erdös discrepancy conjecture
• A Problem of Erdős and Kátai
• scientific article; zbMATH DE number 3914676
• On a problem of Erdős
• scientific article; zbMATH DE number 3073155
• On a problem of Erdős
• On a Problem of Erdos
• On a problem of Erdös

Cites work

• Chains of large gaps between consecutive primes
• Completely multiplicative functions taking values in ${-1,1}$
• Computer-aided proof of Erdős discrepancy properties
• Erdős and arithmetic progressions
• scientific article; zbMATH DE number 3122479 (Why is no real title available?)
• scientific article; zbMATH DE number 687801 (Why is no real title available?)
• scientific article; zbMATH DE number 699709 (Why is no real title available?)
• scientific article; zbMATH DE number 3432350 (Why is no real title available?)
• scientific article; zbMATH DE number 3221521 (Why is no real title available?)
• Large character sums: Pretentious characters and the Pólya-Vinogradov theorem
• Multiplicative functions in short intervals
• Multiplicative number theory. I. Classical theory
• On Character Sums and Primitive Roots^†
• Patterns and complexity of multiplicative functions

Cited in

(42)

• Zero-sum subsequences in bounded-sum \(\{-1,1\}\)-sequences
• Pisot substitution sequences, one dimensional cut-and-project sets and bounded remainder sets with fractal boundary
• Quantifying local randomness in human DNA and RNA sequences using Erdös motifs
• Mini-workshop: Interplay between number theory and analysis for Dirichlet series. Abstracts from the mini-workshop held October 29 -- November 4, 2017
• Rigidity theorems for multiplicative functions
• Multiplicative functions supported on the \(k\)-free integers with small partial sums
• Complex valued multiplicative functions with bounded partial sums
• Additive functions in short intervals, gaps and a conjecture of Erdős
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• Zero-sum subsequences in bounded-sum \(\{-r,s\}\)-sequences
• From the 1-2-3 conjecture to the Riemann hypothesis
• Zero-sum squares in bounded discrepancy \(\{-1,1\}\)-matrices
• The twin prime conjecture
• Chang's lemma via Pinsker's inequality
• Riesz means of certain arithmetic functions
• A note on multiplicative functions resembling the Möbius function
• scientific article; zbMATH DE number 981678 (Why is no real title available?)
• About Erdös discrepancy conjecture
• The Erdős-Szekeres Problem
• Incompleteness, Undecidability and Automated Proofs
• The logarithmically averaged Chowla and Elliott conjectures for two-point correlations
• Equivalence of the Logarithmically Averaged Chowla and Sarnak Conjectures
• Tao's resolution of the Erdős discrepancy problem
• Are monochromatic Pythagorean triples unavoidable under morphic colorings?
• Correlations of multiplicative functions and applications
• Discrepancy in modular arithmetic progressions
• Correlations of multiplicative functions along deterministic and independent sequences
• Good weights for the Erdős discrepancy problem
• Multiplicative functions that are close to their mean
• On the Erdős discrepancy problem
• Divisor-bounded multiplicative functions in short intervals
• The Erdős discrepancy problem over the squarefree and cubefree integers
• The upper logarithmic density of monochromatic subset sums
• Correlations of multiplicative functions in function fields
• Discrepancy theory and related algorithms
• Arithmetic progressions at the journal of the LMS
• Convolution of periodic multiplicative functions and the divisor problem
• Discrepancies of subtrees
• On completely multiplicative 1 sequences that omit many consecutive +1 values
• Modified Dirichlet character sums over the k-free integers
• Bounded exponential sums with multiplicative coefficients
• On Elliott's conjecture and applications

This page was built for publication: The Erdös discrepancy problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2826233)