Lecture on Discrepancy Theory

Introduction

• Discrepancy Theory: Study of how well-balanced or well-distributed sequences of numbers or points can be.
• Example: Plus one, minus one sequences and balancing them.
  • Aim to make sequences equally distributed.

Simple Concepts

• Partial Sums: Balancing consecutive values in a sequence.
  • Easy to make partial sums small by choosing alternating sequences.
  • Random sequences tend to have larger discrepancies.

Advanced Concepts

• Arithmetic Progressions: Making the discrepancy small in arithmetic progressions is challenging.
  • Historical result: Arbitrarily long arithmetic progressions can have high discrepancy.
  • Notable theorem by Roth: Finite sequences have large discrepancies in some arithmetic progressions.

Historical Theorems

• Van der Waerden's Theorem: Arbitrarily long progressions ensure some sub-progressions have no cancellation.
• Szemerédi's Theorem (1975): Specific sign patterns can be found in arithmetic progressions based on density.
• Roth's Discrepancy Theorem: Quantitative approach to discrepancies in finite sequences.

The Erdős Discrepancy Problem

• Problem Statement: Are sums of sequences in homogeneous arithmetic progressions unbounded?
• Equivalent Formulation: Survival problem using left-right movements on a line.
  • Computational exploration has been done to find survival strategies.
• Computational Results:
  • For discrepancy of 3, survival sequence limits have been computed up to 1161 steps.
  • Discrepancy of 4 computations suggest sequences of at least 13,000 steps.

Recent Developments

• Proof: The sums in homogeneous arithmetic progressions are unbounded.
• Polymath Project: Collaborative effort using online platforms.
  • Led to progress in understanding and strategies.

Multiplicative Functions

• Completely Multiplicative Functions: Functions where f(mn) = f(m)f(n).
  • Example: Liouville function and Dirichlet characters.
• Corollary: Partial sums of these functions are unbounded.

Key Insights

• Pair Correlations and Discrepancy: Understanding pair correlations helps determine discrepancies.
  • Correlation decay is crucial for sequence behavior.

Breakthrough Results:

• Matomäki and Radziwiłł's Work: Demonstrated significant cancellation in sums of multiplicative functions.
  • Led to new insights into discrepancy problems.

Techniques and Methods

• Entropy and Information Theory: Utilized Shannon entropy to analyze sequence structure.
  • Suggested potential new approaches in number theory.

Conclusion

• The problem of discrepancy in sequences is rich with historical and recent developments.
• Techniques from different fields, such as information theory, are proving valuable in advancing understanding and solutions.