Polynomial-order oscillations in geometric discrepancy

This paper demonstrates that the optimal homothetic quadratic discrepancy for planar convex bodies does not necessarily follow a single order of growth, but can instead exhibit prescribed polynomial-order oscillations between logarithmic and square-root rates depending on the geometry of the boundary.

The Gist

Imagine you are a master chef trying to sprinkle salt evenly over a giant, irregularly shaped pizza dough. You want the salt to be perfectly uniform, but the dough isn't a perfect circle or a square; it's a weird, bumpy shape.

This paper is about a mathematical game called "Discrepancy." In this game, you drop $N$ points (like grains of salt) onto a shape (the dough). You then ask: "How unevenly are these points distributed?"

If you pick a random spot on the dough and count the salt grains inside it, you compare that number to what you expected to find. The difference is the "discrepancy." The goal is to find the best possible arrangement of points so that this difference is as small as possible.

The Big Question

Mathematicians have known for a long time that the "smoothness" of the dough's edge determines how hard this game is:

• If the dough is a perfect square (sharp corners): The best you can do is a very slow, logarithmic growth of error. It's like a gentle hill.
• If the dough is a perfect circle (smooth curve): The error grows faster, like a steep hill (specifically, the square root of the number of points).

For decades, mathematicians thought: "Okay, if the shape is a polygon, the error grows like $\log N$. If it's smooth, it grows like $\sqrt{N}$. That's it. Those are the only two rules."

The Twist: The "Shape-Shifting" Dough

Thomas Beretti, the author of this paper, says: "Not so fast!"

He proves that you can design a shape that is a chameleon. This shape can change its behavior depending on how many points you throw at it.

• Scenario A: If you throw 100 points, the shape acts like a square (low error).
• Scenario B: If you throw 1,000 points, it suddenly acts like a circle (higher error).
• Scenario C: If you throw 1,000,000 points, it might act like a weird hybrid, growing at a rate somewhere in between.

The paper shows that you can construct a shape that oscillates (swings back and forth) between these different growth rates. It's like a pendulum that doesn't just swing left and right, but changes its speed and height unpredictably as time goes on.

How Did He Do It? (The Two Methods)

The author uses two different "kitchens" to bake these special shapes.

Method 1: The "Russian Doll" Approach (The Implicit Method)

Imagine building a shape by stacking layers of dough on top of each other.

1. Start with a square-ish shape.
2. Add a tiny layer of smooth dough on top.
3. Add a tiny layer of sharp corners on top of that.
4. Repeat this forever, getting smaller and smaller.

Because the layers get infinitely small, the final shape is a perfect limit. By carefully choosing when to add the "sharp" layers and when to add the "smooth" layers, the author forces the shape to behave like a square for a while, then a circle for a while, then back again.

• The Catch: We know the shape exists, but we can't easily describe its edge with a simple formula. It's like a fractal that you can see but can't fully draw.

Method 2: The "Architect" Approach (The Explicit Method)

This is the more impressive trick. Here, the author designs the edge of the shape by hand, like an architect drawing a blueprint.
He creates a curve that looks like a series of different mathematical functions glued together.

• One section looks like $y = x^{1.5}$.
• The next section looks like $y = x^{1.8}$.
• The next looks like $y = x^{1.2}$.

By making these sections transition very smoothly but very quickly, he creates a shape where the "roughness" of the edge changes depending on how closely you look at it.

• The Magic: When you use a small number of points, your "eyes" (the math) see the roughness of one section. When you use a huge number of points, your "eyes" zoom in and see a different section with different roughness.

The "Generic" Truth

The paper also reveals a surprising fact about the universe of shapes.
If you pick a shape completely at random (from the set of all possible convex shapes), it is almost guaranteed to be a "chameleon."

• Most shapes do not have a single, predictable growth rate.
• They are chaotic. They oscillate between being "easy" (logarithmic) and "hard" (polynomial) forever.
• The "nice" shapes (perfect squares or perfect circles) are actually the rare exceptions, like finding a perfect diamond in a pile of gravel.

The Takeaway

This paper shatters the idea that geometric shapes have simple, predictable rules for how they distribute points.

• Old View: Shapes are either "cornery" or "smooth," and that's it.
• New View: Shapes can be complex, shifting personalities. They can be designed to confuse mathematicians by changing their growth rate as you add more data points.

It's a reminder that in mathematics, even something as simple as a "shape" can hide infinite complexity if you know how to look for it. The author didn't just find a weird shape; he showed that weirdness is the norm, and predictability is the exception.

Technical Summary

Here is a detailed technical summary of the paper "Polynomial-order oscillations in geometric discrepancy" by Thomas Beretti.

1. Problem Statement

The paper investigates the optimal homothetic quadratic discrepancy (h.q.d.) of point configurations in the two-dimensional torus $\mathbb{T}^2 = [0, 1)^2$ with respect to a planar convex body $C$.

• Definition: For a set of $N$ points $P \subset \mathbb{T}^2$, the discrepancy with respect to a translated and dilated copy of $C$ is $D(P, \tau + \delta C)$. The homothetic quadratic discrepancy is the $L^2$ average of this quantity over all translations $\tau \in \mathbb{T}^2$ and dilations $\delta \in [0, 1]$:
  $$D_2(P, C) = \int_0^1 \int_{\mathbb{T}^2} |D(P, \tau + \delta C)|^2 \, d\tau \, d\delta.$$
• Objective: The paper seeks to determine the asymptotic behavior of the optimal discrepancy as $N \to \infty$:
  $$\inf_{\#P=N} D_2(P, C).$$
• Context: Previous results established a dichotomy based on the geometry of $C$:
  • If $C$ is a convex polygon, the optimal discrepancy grows as $\log N$ (Beck, 1988; Beck & Chen, 1997).
  • If $C$ has a $C^2$ boundary, the optimal discrepancy grows as $N^{1/2}$ (Brandolini & Travaglini, 2022).
  • Brandolini & Travaglini also showed that for any $\alpha \in [2/5, 1/2)$, there exists a body $C_\alpha$ with growth $N^\alpha$.
• The Gap: It was unknown whether the optimal h.q.d. could exhibit oscillations between different growth orders (e.g., switching between logarithmic and polynomial) or whether a single order of growth is necessary for "generic" convex bodies.

2. Methodology

The author employs two distinct construction methods to create convex bodies with prescribed discrepancy behaviors.

Method 1: Implicit Geometric Construction (The "Limit" Approach)

• Core Idea: Construct a convex body $C$ as the limit of an increasing sequence of convex bodies $\{C_i\}$.
• Mechanism:
  • The sequence alternates between bodies with polygonal boundaries (yielding $\log N$ behavior) and bodies with $C^2$ boundaries (yielding $N^{1/2}$ behavior).
  • A key auxiliary result (Lemma 2.1) establishes that if two sets $A$ and $B$ have a small symmetric difference ($|A \setminus B| \le \eta$), their discrepancies are close: $|D_2(P, A) - D_2(P, B)| \le 4N^2 \eta^{1/2}$.
  • By choosing the symmetric difference $\eta_i$ to decay sufficiently fast, the limit body $C$ inherits the discrepancy properties of the approximating sequence $C_i$ within specific ranges of $N$.
• Topological Argument: The author uses the Baire Category Theorem on the space of convex bodies (endowed with the Hausdorff metric). By showing that bodies with "single-order" growth form a meagre set, they prove that "most" convex bodies exhibit oscillating behavior.

Method 2: Direct Construction via Harmonic Analysis (The "Explicit" Approach)

• Core Idea: Explicitly design the boundary $\partial C$ near a single point (the origin) to control the decay of the Fourier transform of the indicator function $\hat{1}_C$.
• Geometric Design:
  • The boundary is constructed by gluing together segments of monomial curves $y = x^{\beta_i}$ where $\beta_i = \frac{2\alpha_i}{2-3\alpha_i}$.
  • The curvature of these segments is strictly decreasing and tends to infinity at the origin. The sequence of curvatures is tuned to ensure that at different scales (distances from the origin), the boundary locally resembles different monomials.
• Fourier-Analytic Link:
  • The paper utilizes the relationship between the chord length of the convex body and the decay of its Fourier transform (Lemma 3.2).
  • For a body with local geometry $y \sim |x|^\beta$, the chord length decays as $\lambda^{1/\beta}$. This dictates the decay of $|\hat{1}_C(\xi)|^2$.
  • Using Parseval's identity, the discrepancy is expressed as a sum involving $|\hat{1}_C(n)|^2$ and exponential sums over the point set.
• Bounds:
  • Lower Bound: Uses a Cassels-Montgomery lemma to estimate exponential sums from below, selecting point sets that maximize the discrepancy based on the specific Fourier decay of the constructed body.
  • Upper Bound: Constructs a specific "lattice-like" point set (a product of arithmetic progressions) that minimizes the discrepancy by aligning with the zeros of the Fourier transform of the specific body geometry.

3. Key Contributions and Results

Theorem 1.5: Oscillations between Logarithmic and Polynomial Growth

The author proves that for any sequence of exponents $\{\alpha_i\} \in \{0, 1/2\}$, there exists a convex body $C$ and a sequence of intervals $[N_i, N_i + q_i]$ such that the optimal discrepancy oscillates between:

• $\log N$ (when $\alpha_i = 0$)
• $N^{1/2}$ (when $\alpha_i = 1/2$)
  This is achieved via the implicit geometric construction.
• Significance: This demonstrates that the optimal discrepancy does not necessarily converge to a single power law. Furthermore, the set of convex bodies with a single order of growth is meagre (topologically small) in the space of all planar convex bodies.

Theorem 1.6: Prescribed Polynomial Oscillations

The author proves that for any sequence of exponents $\{\alpha_i\} \subset (2/5, 1/2)$, there exists a convex body $C$ such that the optimal discrepancy oscillates between $N^{\alpha_i - \epsilon_i}$ and $N^{\alpha_i + \epsilon_i}$ on specified intervals.

• Significance: This extends the range of achievable growth rates beyond the previously known single-exponent bodies. It shows that one can "program" the discrepancy to switch between different polynomial orders by carefully designing the local curvature of the boundary.

4. Technical Significance

1. Resolution of the "Single Order" Conjecture: The paper definitively answers the question of whether a single order of growth is necessary for the optimal h.q.d. The answer is no. The behavior is highly sensitive to the fine geometric structure of the boundary.
2. Baire Category Result: By showing that bodies with non-oscillating (single-order) discrepancy are meagre, the paper suggests that "generic" convex bodies in the Hausdorff metric space exhibit complex, oscillating discrepancy behavior.
3. Synthesis of Geometry and Analysis: The work bridges geometric measure theory (chord lengths, curvature) with harmonic analysis (Fourier decay, exponential sums). It provides a concrete mechanism: local curvature $\to$ chord decay $\to$ Fourier decay $\to$ discrepancy order.
4. Construction Techniques: The paper introduces a novel method of constructing convex bodies by "gluing" monomial curves with rapidly varying curvatures to create multi-scale geometric features that influence the discrepancy at different scales of $N$.

5. Conclusion

Thomas Beretti's work fundamentally alters the understanding of geometric discrepancy for convex bodies. It moves beyond the binary classification of polygons vs. smooth bodies to reveal a rich landscape of intermediate and oscillating behaviors. The results imply that the optimal discrepancy is not an intrinsic property of the "smoothness" of a body alone, but rather a complex interplay between the specific local geometry of the boundary and the scale of the point configuration. The existence of bodies with prescribed stationary orders of growth suggests that discrepancy theory is capable of encoding arbitrary growth patterns through geometric design.