ESTIMATES ON THE CONCENTRATION FUNCTION OF

SETS IN R^{d}: NOTES ON LECTURES OF OSKOLKOV

RALPH HOWARD

DEPARTMENT OF MATHEMATICS UNIVERSITY OF SOUTH CAROLINA COLUMBIA, S.C. 29208, USA

                           HOWARD@MATH.SC.EDU

Contents

1. Introduction 1 2. Statement of the problem and application of the Fourier transform.

2 2.1. The Problem. 2 2.2. Reduction to an analytic problem. 3 2.3. A choice of the test function φ in one dimension and for D an

interval. 5

2.4. The test function for D a cube in R^{d}. 6 3. Rearrangement inequalities and their applications. 7 3.1. The basic rearrangement inequalities. 7 3.2. A trick for reducing the dimension of the problem. 9 3.3. Application of the rearrangement inequalities to integrals of

products of cosines. 10

4. Estimates on the concentration. 14 4.1. A one dimensional result. 14 4.2. Estimates when a positive proportion of the vectors have at

least unit length. 15

4.3. Estimates when the many of the vectors are not all close to a

hyperplane. 16

References 16

1. Introduction

This set of notes is a result of a very pleasant interaction between the analysts, combinatorsts, and geometers in the mathematics department at the University of South Carolina. Let v_{1}, …, v_{n} be vectors in R^{d} so that any subset of {v_{1}, …, v_{n}} of size d is linearly independent (for convenience say that such a set is in general position). Then Jerry Griggs has posed the problem of giving good upper and lower bounds on the number

C(d, n) := max_{v_{1},...,v_{n}} max_{y∈R^{d}} #{(ε_{1}, …, ε_{n}) : ε_{k} = ±1 and ∑_{k=1}^{n} ε_{k}x_{k} = y}

where v_{1}, …, v_{n} varies sets in general position. By using a clever combination of linear algebra, probability, and elementary number theory Griggs [1] was given a lower bound

C(d, n) ≥ C(d) (\frac{1}{n\sqrt{n}})^{d} 2^{n}.

In the paper [2] Halász gives upper bounds for a more general problem with imply that

C(d, n) ≤ C′(d)\frac{1}{n} (\frac{1}{\sqrt{n}})^{d} 2^{n}.

Halász’s paper uses quite a bit of machinary from probability theory and in lectures in our combintoric’s seminar Kostya Oskolkov showed that the probabality could be avoided and that Halász’s result can be reduced to estimating certian integrals whoses integrands are products of absolute values of cosines. My contribution to this project is noting that in some cases these integrals can be estimated by use of rearrangment inequalites. This very much simplifies the proof of Thoerm 1 in [2]. However this only leads to the upper bound

C(d, n) ≤ C′′(d) (\frac{1}{\sqrt{n}})^{d} 2^{n}.

Unfortunately there seem to be structural reasons why the simplier methods used in the notes here can not give the stronger result.

The notes here are basically an expanded version of Oskolkov’s lectures with some proofs and references added on the use of rearrangement inequalities (the basic reference here is the wonderful book [3] of Leib and Loss). The main result here (Theorem 4.3) is a slight refinement of Theorem 1 of [2] in that all constants are given explicitly^{1}. I hope that these notes are readable to non-analysts and in particular to combinatorsts.

2. Statement of the problem and application of the Fourier transform.

2.1. The Problem. Let v_{1}, …, v_{n} ∈ R^{d} be n vectors in the d dimensional Euclidean space R^{d} and D ⊂ R^{d} a bounded domain and define

N_{D} = #{(ε_{1}, …, ε_{n}) : ε_{k} = ±1 and ∑_{k=1}^{n} ε_{k}v_{k} ∈ D}.

1Note however that “explicit” does not mean “correct”. This is a technical subject and the amount of proof reading required to insure the correctness of all the constants was more than I was up for.

Then N_{D} is the number, counted with multiplicity, of the sums ±v_{1}±⋯±v_{n} that are in D. Thus different choice of ε_{1}, …, ε_{n} that give rise to the same sum in D each count in computing D. In the extreme case where v_{k} = 0 for all k all the sums ∑_{k=1}^{n} ε_{k}v_{k} are the same and equal to 0, but in this case if 0 ∈ D we have N_{D} = 2^{n}. The translate of D by y ∈ R^{d} is D + y = {x + y : x ∈ D}. Define N_{D} by

N_{D} = max_{y∈R^{d}} N_{D+y}

The number N_{D} is thus just the maximum number of sums ∑_{k=1}^{n} ε_{k}v_{k} (counted with multiplicity) that can be captured by a translate of D and is called the concentration. We wish to give a method for estimating N_{D} form above in terms of the geometry of D and v_{1}, …, v_{n}. We will start by estimating N_{D}, but the resulting inequality will end up being “translation invariant” and thus also gives a bound on N_{D}.

2.2. Reduction to an analytic problem. We first give an integral formula for N_{D} using a trick from analytic number theory. For any subset A ⊂ R denote the Lebesgue measure of A by |A|. Let r_{1}, …, r_{n}: [0, 1] → R be independent random variables all with the distribution that takes on the values ±1 each with probability 1/2. (Those wishing to avoid all use of probability see Remark 2.3 below.) A concrete choice of r_{1}, …, r_{n} is the Rademacher functions given by r_{k}(t) = sign sin(2^{k}πt) in which case it is easy to check that

|\{t ∈ [0, 1] : r_{k}(t) = +1\}| = |\{t ∈ [0, 1] : r_{k}(t) = −1\}| = \frac{1}{2}.

It takes a little more work to show these are independent as random variables, but this is still elementary. Let

S(t) := ∑_{k=1}^{m} r_{k}(t)x_{k}.

Then, because each r_{k}(t) takes on the values ±1 and the r_{k} are independent random variables, as t ranges over [0, 1] the function S(t) ranges over all the sums ∑ ε_{k}x_{k} and for a give choice of ε_{1}, …, ε_{n} the measure of the set of t that realizes this sum is 1/2^{n}. Denote by χ_{D} is the characteristic function of D (i.e. χ_{D}(x) = 1 if x ∈ D and χ_{D}(x) = 0 if x ∉ D) then from the properties of S(t) just given

N_{D} = 2^{n} ∫_{0}^{1} χ_{D}(S(t)) dt.

If φ: R^{d} → R is a function that satisfies

φ ≥ χ_{D}

then there is the obvious inequality

N_{D} ≤ 2^{n} ∫_{0}^{1} φ(S(t)) dt. (2.1)

The reason we wish to replace χ_{D} a function φ ≥ χ_{D} is that we will be using Fourier transform methods and the Fourier transform of χ_{D} is rather unpleasant (for example it is not in L^{1}(R^{d})) and we will be able to make choices of φ whose Fourier transforms are easier to work with.

Our convection on the constants in the Fourier transform are as follows. If f ∈ L^{1}(R^{d}) then its Fourier transform is

f̂(ξ) = (2π)^{− \frac{d}{2}} ∫_{R^{d}} f(x)e^{−i⟨x,ξ⟩} dx

where ⟨ , ⟩ is the standard inner product on R^{d} and dx is the standard volume measure. If f and f̂ are both in L^{1} then the Fourier inversion formula holds and is given by

f(x) = (2π)^{− \frac{d}{2}} ∫_{R^{d}} f̂(ξ)e^{i⟨x,ξ⟩} dξ.

We now let φ ≥ χ_{D} be a function so that both φ and φ̂ are in L^{1} and use the Fourier inversion formula in the inequality (2.1) and invert the order of integration to get

N_{D} ≤ 2^{n}(2π)^{− \frac{d}{2}} ∫_{R^{d}} φ̂(ξ) ∫_{0}^{1} e^{i⟨S(t),ξ⟩} dt dξ. (2.2)

To simplify this note that as each r_{k}(t) takes on the values +1 and −1 each with measure 1/2 for any real number c

∫_{0}^{1} e^{ir_{k}(t)c} dt = \frac{1}{2}e^{ic} + \frac{1}{2}e^{−ic} = cos(c).

Using this, the definition of S(t), and the independence of r_{1}, …, r_{n}

∫_{0}^{1} e^{i⟨S(t),ξ⟩} dt = ∫_{0}^{1} e^{i(r_{1}(t)⟨x_{1},ξ⟩+···+r_{n}(t)⟨x_{n},ξ⟩)}dt

= ∫_{0}^{1} ∏_{k=1}^{n} e^{ir_{k}(t)⟨x_{k},ξ⟩}dt

= ∏_{k=1}^{n} ∫_{0}^{1} e^{ir_{k}(t)⟨x_{k},ξ⟩}dt

= ∏_{k=1}^{n} cos⟨x_{k}, ξ⟩. (2.3)

Putting this back in (2.2) gives

N_{D} ≤ (2π)^{− \frac{d}{2}} ∫_{R^{d}} φ̂(ξ) ∏_{k=1}^{n} cos⟨x_{k}, ξ⟩ dξ

≤ (2π)^{− \frac{d}{2}} ∫_{R^{d}} |φ̂(ξ)| ∏_{k=1}^{n} | cos⟨x_{k}, ξ⟩| dξ (2.4)

Thus we have done most of the work toward proving:

Proposition 2.1 (Oskolkov’s Lemma). Let D be a bounded domain in R^{d} and φ a function so that φ ≥ χ_{D} and both φ and φ̂ are in L^{1}(R^{d}). Then

N_{D} ≤ (2π)^{− \frac{d}{2}} ∫_{R^{d}} |φ̂(ξ)| ∏_{k=1}^{n} | cos⟨x_{k}, ξ⟩| dξ. (2.5)

Proof. For any y ∈ R^{d} and function f: R^{d} → R let τ_{y}f(x) := f(x−y) be the translate of f by y. Then τ_{y}χ_{D} = χ_{D+y}. Let φ ≥ χ_{D} as in the statement of the proposition. Then τ_{y}φ ≥ χ_{D+y}. The Fourier transform of a translation is given by τ̂_{y}φ(ξ) = e^{−i⟨ξ,y⟩}φ̂(ξ) and therefore |τ̂_{y}φ(ξ)| = |φ̂(ξ)|. Using this in (2.4) gives

N_{D+y} ≤ (2π)^{− \frac{d}{2}} ∫_{R^{d}} |φ̂(ξ)| ∏_{k=1}^{n} | cos⟨x_{k}, ξ⟩| dξ.

The right side of this is independent of y and (2.5) follows.

Remark 2.2. We are now in the situation of many proofs in analysis. We have the inequality (2.5) which depends on an arbitrary “test function” φ. The game now becomes to find a good, or at least a manageable choice, of φ. We will start by looking at choices for φ in the one dimensional case and then using these to get construct φ in higher dimensions in the case D is a cube.

Remark 2.3. The basic property of the functions r_{k}(t) used was the computation 2.3. Using the Rademacher functions this calculation can be directly form the definition of the r_{k}(t)’s and all mention of probability thus avoided.

2.3. A choice of the test function φ in one dimension and for D an interval. First we review a little about the Fourier transform in for functions on R^{d}. If f, g ∈ L^{1}(R^{d}) then the convolution f ∗ g of f and g is given by

f ∗ g(x) = ∫_{R^{d}} f(x − y)g(y) dy = ∫_{R^{d}} f(y)g(x − y) dy.

This is also in L^{1}(R^{d}). The Fourier transform and convolution are related by

(2π)^{−d/2}{ \atop f ∗ g}(ξ) = f̂(ξ)ĝ(ξ).

(The factor on the left is due to the choice of where we are putting the 2π’s in the definition of the Fourier transform.) Back in the one dimensional case let f(ξ) = χ_{[−a,a]}(ξ) be the characteristic function of an interval of length 2a centered at the origin. Then

f̂(x) = \frac{1}{\sqrt{2π}} ∫_{−a}^{a} e^{ixξ}dξ = \sqrt{\frac{2}{π}} \frac{sin(ax)}{x}.

Then

\frac{1}{\sqrt{2π}} { \atop f ∗ f}(x) = f̂(x)^{2} = \frac{2}{π} \frac{sin^{2}(ax)}{x^{2}}.

The smallest positive zero of sin(ax)/x is at x = π/a and the function sin(ax)/x is decreasing on [0, π/a]. Let r = π/a so that a = π/r and r/2 = π/(2a). For these values of r and a the smallest values of sin^{2}(ax)/x^{2} on the interval [−r/2, r/2] occur when x = ±r/2 and the smallest value is

\frac{sin^{2}(ra/2)}{(r/2)^{2}} = \frac{4}{r^{2}} .

Therefore

\frac{\sqrt{2π}r^{2}}{16} { \atop f ∗ f}(x) = \frac{r^{2} sin^{2}(πx/r)}{4x^{2}} ≥ 1 for x ∈ [−r/2, r/2].

We also can compute f ∗ f explicitly and get

f ∗ f(ξ) = max(0, 2a − |ξ|) = max(0, 2π/r − |ξ|^{2}).

Lemma 2.4. If φ_{1} : R → [0, ∞) is given by

φ_{1}(x) = \frac{r^{2} sin^{2}(πx/r)}{4x^{2}}

then φ_{1} ≥ χ_{[−r/2,r/2]}, φ_{1} ∈ L^{1}(R), and

φ̂_{1}(ξ) = \frac{\sqrt{2π}r^{2}}{16} max(0, 2π/r − |ξ|)

which is supported in [−2π/r, 2π/r].

Proof. On the set of functions symmetric about the origin (that is f(−x) = f(x) the Fourier transform and its inverse are given by the same formula. Therefore applying the inverse transform to the calculations above gives the result.

2.4. The test function for D a cube in R^{d}. Let Q(r) be the cube [−r/2, r/2]^{d} be the centered cube in with side of length r in R^{d}, and let x_{1}, …, x_{d} be the coordinate functions on R^{d}.

Lemma 2.5. Define a function φ: R^{d} → [0, ∞) by

φ(x) = (\frac{r^{2}}{4} )^{d} ∏_{j=1}^{d} \frac{sin^{2}(πx_{j}/r)}{x_{j}^{2}}

then φ ∈ L^{1}(R^{d}), φ ≥ χ_{Q(r)},

φ̂(ξ) = (\frac{\sqrt{2π}r^{2}}{16} )^{d} ∏_{j=1}^{d} max(0, 2π/r − |ξ_{j}|)

which is supported in Q(2π/r) and satisfies the bound

|φ̂(ξ)| ≤ (\frac{(2π)^{3/2}ra}{16})^{d} .

Proof. With the notation of Lamma 2.4 we have φ(x) = φ_{1}(x_{1})φ_{1}(x_{2}) ⋯ φ_{1}(x_{d}) and the results follow from that lemma.

Proposition 2.6. Let Q(r) be the cube with sides parallel to the coordiante axis in R^{d} and edge lenght of r. Then the concentration of v_{1}, …, v_{k} satisfies

N_{Q(r)} ≤ 2^{n} (\frac{πr}{8} )^{d} ∫_{Q(2π/r)} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ.

Proof. We use the test function φ of Lemma 2.5 (and the bounds given there) in Proposition 2.1 to get:

N_{Q(r)} ≤ (2π)^{− \frac{d}{2}} ∫_{R^{d}} |φ̂(ξ)| ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ

≤ 2^{n}(2π)^{− \frac{d}{2}} (\frac{(2π)^{3/2}ra}{16})^{d} ∫_{Q(2π/2)} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ

= 2^{n} (\frac{πr}{8} )^{d} ∫_{Q(2π/r)} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ

This completes the proof.

Remark 2.7. To get an idea if this estimate is any good we look at the extreme case where v_{k} = 0 for all k. Then N_{D} = 2^{n} for any D. The estimate of the last proposition gives (using that cos⟨v_{k}, ξ⟩ = cos(0) = 1)

N_{Q(r)} ≤ 2^{n} (\frac{πr}{8} )^{d} Vol(Q(2π/r)) = 2^{n} (\frac{π^{2}}{4} )^{d} ≤ 2^{n}(2.468)^{d}

which is not all that good, but not outrageously bad.

3. Rearrangement inequalities and their applications.

3.1. The basic rearrangement inequalities. Let A ⊂ R^{d} be a Lebesgue measurable set and denote the measure of A by |A|. Define the symmetirzation A^{∗} of A to be the closed ball centered at the origin such with the same measure as A. Thus in one dimension

A^{∗} := [−|A|/2, |A|/2]

and in two dimensions

A^{∗} := B(0, (|A|/π)^{1/2}).

More generally if define ω(d) to be the volume of the unit ball in R^{d} then for A ⊂ R^{d}

A^{∗} := B(0, (|A|/ω(d))^{1/d}).

We now wish to extend this idea of syemmtrization from sets to non-negative functions. For a charactertic function χ_{A} of a set how to do this is clear:

χ_{A}^{∗} := χ_{A^{∗}}

We now use that any non-negative function can be expressed as an integral of the characteristic functions of the sets {f ≥ t} (which is a standard abbreviation for {x : f(x) ≥ t}) as follows

f(x) = ∫_{0}^{f(x)} 1 dt = ∫_{0}^{∞} χ_{{f≥t}}(x) dt. (3.1)

This representation of f is sometimes called the layer cake representation of f. Note that this, along with Fubini’s theorem, implies

∫_{R^{d}} f(x) dx = ∫_{R^{d}} ∫_{0}^{∞} χ_{{f≥t}}(x) dt dx
= ∫_{0}^{∞} χ_{{f≥t}}(x) dx dt
= ∫_{0}^{∞} |{x : f(x) ≥ t}| dt.

We now define the symmetric decreasing rearrangement of a nonnegative measurable function f by

f^{∗}(x) := ∫_{0}^{∞} χ_{{f≥t}}^{∗}(x) dt. (3.2)

The basic properties of f^{∗} are that it is monotone decreasing as a function of |x|:

|x| ≤ |y| implies f^{∗}(x) ≥ f^{∗}(y). (3.3)

Letting |x| = |y| (so that |x| ≤ |y| and |y| ≤ |x|) this implies f^{∗} is symmetric

|x| = |y| implies f^{∗}(x) = f^{∗}(y).

A little less obvious but very important is that f and f^{∗} are equi-measurable in the sense that

|{f^{∗} ≥ t}| = |{f ≥ t}| (3.4)

for all t.

The two properties (3.3) and (3.4) come close to characterizing f^{∗} and in fact do characterize f^{∗} up to a set of measure zero.

What makes the symmetric decreasing rearrangement interesting to us is

Theorem 3.1 (Basic rearrangement inequality). Let f_{1}, …, f_{m}: R^{d} → [0, ∞) be non-negative measurable functions. Then

∫_{R^{d}} f_{1}(x)f_{2}(x) ⋯ f_{m}(x) dx ≤ ∫_{R^{d}} f_{1}^{∗}(x)f_{2}^{∗}(x) ⋯ f_{m}^{∗}(x) dx.

Proof. We first consider the case where each f_{k} = χ_{A_{k}} is the characteristic function of a measurable set. By reordering we can assume that A_{1} has the smallest measure of the sets A_{1}, …, A_{m}. Then the product f_{1}f_{2} ⋯ f_{m} is just χ_{A_{1}∩···∩A_{m}}, that is the characteristic function of the intesection A_{1}∩⋯∩A_{m}. But A_{1} ∩ ⋯ ∩ A_{m} ⊆ A_{1} and so

∫_{R^{d}} f_{1}(x)f_{2}(x) ⋯ f_{m}(x) dx = |A_{1} ∩ ⋯ ∩ A_{m}| ≤ |A_{1}| (3.5)

But in this case f_{k}^{∗} = χ_{A_{k}^{∗}} and |A_{k}^{∗}| = |A_{k}|. Thus A_{1}^{∗} will have the smallest measure of the sets A_{1}^{∗}, …, A_{m}^{∗}. But as all the A_{k}^{∗} are closed balls centered at the origin this implies A_{1}^{∗} ∩ ⋯ ∩ A_{m}^{∗} = A_{1}^{∗}. Thus

∫_{R^{d}} f_{1}^{∗}(x)f_{2}^{∗}(x) ⋯ f_{m}^{∗}(x) dx = |A_{1}^{∗} ∩ ⋯ ∩ A_{m}^{∗}| = |A_{1}^{∗}| = |A_{1}|.

Putting this together with (3.5) implies the result in the case all the f_{k} are characteristic functions. In the general case we use the layer cake representation (3.1) to reduce to the case of characteristic functions. In the following we interchange the order of integration without comment.

∫_{R^{d}} f_{1}(x)f_{2}(x) ⋯ f_{m}(x) dx

= ∫_{0}^{∞} ⋯ ∫_{0}^{∞} ∫_{R^{d}} χ_{{f_{1}≥t_{1}}}(x) ⋯ χ_{{f_{m}≥t_{m}}}(x) dx dt_{1} ⋯ dt_{m}

≤ ∫_{0}^{∞} ⋯ ∫_{0}^{∞} ∫_{R^{d}} χ_{{f_{1}^{∗}≥t_{1}}}(x) ⋯ χ_{{f_{m}^{∗}≥t_{m}}}(x) dx dt_{1} ⋯ dt_{m}

= ∫_{R^{d}} f_{1}^{∗}(x)f_{2}^{∗}(x) ⋯ f_{m}^{∗}(x) dx.

This completes the proof.

3.2. A trick for reducing the dimension of the problem. The next result is basically just a technical lemma that shows us in some cases to reduce a problem in estimating a function of one function of several variables to a several (hopefully easier) estimates of functions of one variable. First some notation. For x ∈ R^{d} let x_{1}, …, x_{d} be the coordinates of x (so that x = (x_{1}, …, x_{d})). Then for 1 ≤ j ≤ d and f(x) = (x_{1}, …, x_{d}) let

S_{j}^{∗}f(x_{1}, …, x_{d}) = \{ \begin{matrix}symmetric decreasing rearrangment of f with \\ respect to x_{j} holding other variables fixed. \end{matrix}

This one variable version of symmetrization is called Steiner symmetrization after Steiner who introduced it early in the last century and who seems to have been to use symmetrization methods in proving geometric inequalities.

Proposition 3.2. Let F: R^{d} → [0, ∞) be a nonnegative measurable function that can be factored as

F (x) = F (x_{1}, …, x_{d}) = f_{1}(x_{1})f_{2}(x_{1}, x_{2})f_{3}(x_{1}, x_{2}, x_{3}) ⋯ f_{d}(x_{1}, …, x_{d})

where f_{j} only depends on x_{1}, …, x_{j}. Assume that for each j there is a symmetric deceasing function g_{j}(t) of one variable so that

S_{j}^{∗}f_{j}(x_{1}, …, x_{j}) ≤ g_{j}(x_{j})

and also assume that there is a symmetric decreasing function G: R^{d} → [0, ∞) so that

g_{1}(x_{1})g_{2}(x_{2}) ⋯ g_{d}(x_{d}) ≤ G(x_{1}, …, x_{d}) = G(x).

Then

F^{∗}(x) ≤ G(x)

for all x.

Proof. It is not hard to verify from the definitions that

|{x :F (x) ≥ t}| = |{(x_{1}, …, x_{d}) : f_{1}(x_{1}) ⋯ f_{d}(x_{1}, …, x_{d}) ≥ t}|
≤ |{(x_{1}, …, x_{d}) : f_{1}(x_{1}) ⋯ f_{d−1}(x_{1}, …, x_{d−1})g_{d}(x_{d}) ≥ t}|

≤ |{(x_{1}, …, x_{d}) : f_{1}(x_{1}) ⋯ f_{d−2}(x_{1}, …, x_{d−2})g_{d−1}(x_{d−1})g_{d}(x_{d}) ≥ t}|

⋮
≤ |{(x_{1}, …, x_{d}) : g_{1}(x_{1}) ⋯ g_{d−1}(x_{d−1})g_{d}(x_{d}) ≥ t}|
≤ |{(x_{1}, …, x_{d}) : G(x_{1}, …, x_{d}) ≥ t}|.

And so F^{∗}(t) ≤ G^{∗}(t) = G(t) (where G^{∗} = G as G is symmetric and a monotone decreasing function of |x|). This completes the proof.

3.3. Application of the rearrangement inequalities to integrals of products of cosines.

Lemma 3.3. Let f : [−R, R] → [0, 1] be given by f(x) = | cos(ax + b)| where a is an integral multiple of π/(2R) (this implies that 2R is a period of f(x))). Then

f^{∗}(x) = cos(πx/(2R)).

Proof. Doing this in terms of the definition (3.2) is hard work, but by using the characterization (3.3) and (3.4) and drawing a picture this becomes more or less clear.

Lemma 3.4. Let f : [−R, R] → [0, 1] be given by f(x) = | cos(ax+b)| where a ≥ π/(2R). Then

f^{∗}(x) ≤ cos(πx/(4R)).

Proof. As a ≥ π/(2R) the smallest P_{min} period of f(x) is ≤ 2R. Let R_{1} be the smallest number ≥ R so that 2R_{1} is a period of f(x). Then R_{1} ≤ R. Let f_{1}(x) be the natural extension of f(x) to [−R_{1}, R_{1}] (that is f_{1}(x) = | sin(ax+ b)| for |x| ≤ R_{1}). From the characterization of symmetric rearrangements given by (3.3) and (3.4) we clearly have f^{∗}(x) ≤ f_{1}^{∗}(x) for |x| ≤ R. But then the last lemma and R_{1} ≤ R implies

f^{∗}(x) ≤ f_{1}^{∗}(x) = cos(πx/(2R_{1})) ≤ cos(πx/(4R)).

This completes the proof.

Lemma 3.5. Let f : [−R, R] → [0, 1] be given by f(x) = | cos(ax+b)| where a ≤ π/(2R). Then

f^{∗}(x) ≤ cos(ax).

Proof. An exercise.

Lemma 3.6. For |t| ≤ π/2 the inequality

cos(t) ≤ e^{−t^{2}/2}

holds.

Proof. Anther exercise.

Lemma 3.7. Let f_{1}, …, f_{d}: [−R, R]^{d}: → R be d functions given by

f_{j}(x_{1}, …, x_{j}) = | cos(a_{j}x_{j} + b_{j}(x_{1}, …, x_{d−1}))|.

(thus f_{j} only depends on the variables x_{1}, …, x_{j} and b_{j} only depends on x_{1}, …, x_{j−1}). Let F (x) = F (x_{1}, …, x_{d}) be

F (x) = f_{1}(x) ⋯ f_{d}(x)

the product of the f_{j}. Assume that |a_{j}| ≥ π/(2R). Then

F^{∗}(x_{1}, …, x_{d}) ≤ e^{− \frac{1}{2} \frac{π^{2}}{16R^{2}} (x_{1}^{2}+···+x_{d}^{2})}

Remark 3.8. In terms of other notation used here [−R, R]^{d} = Q(2R).

Proof. Let g_{j}(t) = | cos(πt/(4R))| Then by Lemma 3.4 the inequality

S_{j}^{∗}f_{j}(x_{1}, …, x_{j}) ≤ g_{j}(x_{j}) = | cos(πx_{j}/(4R))|.

As |x_{j}| ≤ R we have |πx_{j}/(4R)| ≤ π/4 < π/2 and this by Lemma 3.6 we can estimate the product

g_{1}(x_{1})g_{2}(x_{2}) ⋯ g_{d}(x_{d}) ≤ e^{\frac{−π^{2}x^{2}_{1}}{32R^{2}}} e^{\frac{−π^{2}x^{2}_{2}}{32R^{2}}} ⋯ e^{\frac{−π^{2}x^{2}_{d}}{32R^{2}}} = e^{− \frac{1}{2} \frac{π^{2}}{16R^{2}} (x_{1}^{2}+···+x_{d}^{2})}.

The function G(x_{1}, …, x_{d}) = e^{− \frac{1}{2} \frac{π^{2}}{16R^{2}} (x_{1}^{2}+···+x_{d}^{2})} is symmetric and decreasing so that Proposition 3.2 applies. This completes the proof.

Proposition 3.9. Let v_{1}, …, v_{n} ∈ R^{d} be n vectors in R^{d} and let m ≤ n. Assume that for any unit vector u ∈ R^{d} that for at least m of the indices k the inequality

|⟨v_{k}, u⟩| ≥ π/(2\sqrt{d}R)

holds. Then

∫_{Q(2R)} ∏_{k=1}^{n} | cos⟨ξ, v_{k}⟩| dξ ≤ (\frac{8dR}{\sqrt{2π}} )^{d} (\frac{1}{\sqrt{m}})^{d}

Proof. Let call an ordered set (v_{k_{1}}, …, v_{k_{d}}) from the list v_{1}, …, v_{n} nice iff the vectors v_{k_{1}}, …, v_{k_{d}} are linearly independent, |v_{1}| ≥ π/(2\sqrt{d}R) and for 2 ≤ j ≤ d the length of the orthogonal projection of v_{k_{j}} onto span(v_{k_{1}}, …, v_{k_{j−1}})^{⊥} has length ≥ π/(2\sqrt{d}R). If the number m in the statement of the proposition is ≥ d then we can construct a nice ordered set (v_{k_{1}}, …, v_{k_{d}}) as follows. First choose v_{k_{1}} so that |v_{k_{1}}| ≥ π/(2\sqrt{d}R) and for future use let e_{1} := v_{k_{1}}/|v_{k_{1}}| be the unit vector in the direction of v_{k_{1}}. Now assume that v_{k_{1}}, …, v_{k_{j−1}} have been defined. Then let u ∈ span(v_{k_{1}}, …, v_{k_{j−1}})^{⊥} be a unit vector.

Then there is a vector v_{k_{j}} so that |⟨v_{k_{j}}, u⟩| ≥ π/(2\sqrt{d}R). This imples that if v_{k_{j}}^{⊥} is the orthogonal projection of v_{k_{j}} onto span(v_{k_{1}}, …, v_{k_{j−1}})^{⊥} then |v_{k_{j}}^{⊥}| ≥ π/(2\sqrt{d}R). Now let e_{k} := v_{k_{j}}^{⊥}/|v_{k_{j}}^{⊥}| be the unit vector in the direction of v_{k_{j}}^{⊥}. Then (v_{k_{1}}, …, v_{k_{d}}) is nice and also e_{1}, …, e_{d} is an orthonormal basis of R^{d} so that

(3.6) span(e_{1}, …, e_{j}) = span(v_{k_{1}}, …, v_{k_{j}}) and |⟨e_{j}, v_{k_{j}}⟩| ≥ π/(2\sqrt{d}R)

for j = 1, …, d.

Let p be the largest integer so that pd ≤ m (thus p ≤ m/d). Then be doing the construction above p times we can find p nice ordered sets with no elements in common and be reordering we can assume that the nice ordered sets are

(v_{1}, …, v_{d}), (v_{d+1}, …, v_{2d}), …, (v_{ℓd+1}, …, v_{(ℓ+1)d}), …, (v_{(p−1)d+1}, …, v_{pd}).

Let F_{ℓ} be the function

F_{ℓ}(ξ) = | cos⟨ξ, v_{ℓd+1}⟩|| cos⟨ξ, v_{ℓd+2}⟩| ⋯ | cos⟨ξ, v_{(ℓ+1)d}⟩|.

Then

∏_{k=1}^{n} | cos⟨ξ, v_{k}⟩| = ∏_{ℓ=1}^{p} F_{ℓ}(x) · ∏_{k=pd+1}^{n} | cos⟨ξ, v_{k}⟩| ≤ ∏_{ℓ=1}^{p} F_{ℓ}(x) (3.7)

We now estimate the symmetric rearrangement of F_{1}. Let e_{1}, …, e_{d} be the orthonormal basis of R^{d} associated with the nice ordered set v_{1}, …, v_{d} as in (3.6). Then do an orthogonal change of variables η = P ξ (thus P is an orthogonal matrix) so that in the variables η = (η_{1}, …, η_{d}) the η_{j} axis is in the direction of e_{j}. Let Q′(2R) be the image of the cube Q(2R) under this change of variables. Then Q′(2R) ⊂ Q(2\sqrt{d}R) (where the cube Q(2\sqrt{d}R) is defined with respect to η coordinate system). Let F′_{ℓ}(η) be F_{ℓ} in the new coordinate system (and we extend F′_{ℓ} to Q(2\sqrt{d}R) so that in Q(2\sqrt{d}R) is still given by the same formulas as in Q′(2R)). Now in the coordinate system η_{1}, …, η_{d} we have

F′_{1}(η) = ∏_{j=1}^{d} | cos(a_{j}η_{j} + b_{j}(η_{1}, …, η_{j−1}))|

where |a_{j}| = |⟨v_{j}, e_{j}⟩| ≥ π/(2\sqrt{d}R). Therefore by Lemma 3.7 (with R replaced by \sqrt{d}R) we have

(F′_{1})^{∗}(η_{1}, …, η_{d}) ≤ e^{− \frac{1}{2} \frac{π^{2}}{16\sqrt{d}R^{2}} |η|^{2}}

Translating this back to the original coordinate system gives

F_{1}^{∗} ≤ e^{− \frac{1}{2} \frac{π^{2}}{16\sqrt{d}R^{2}} |η|^{2}}.

Clearly the same estimate will hold for F_{ℓ} with 1 ≤ ℓ ≤ p. Thus by the basic rearrangement inequality we have

∫_{Q(2R)} ∏_{ℓ=1}^{p} F_{ℓ}(ξ) dξ ≤ ∫_{R^{d}} ∏_{ℓ=1}^{p} F_{ℓ}^{∗}(ξ) dξ

≤ ∫_{R^{d}} e^{− \frac{1}{2} \frac{mπ^{2}}{16\sqrt{d}R^{2}} |η|^{2}} dξ

= (\sqrt{2π})^{d} (\frac{1}{\sqrt{(pπ^{2})/(16dR^{2})}})^{d}

≤ (\frac{8dR}{\sqrt{2π}} )^{d} (\frac{1}{\sqrt{m}})^{d} .

Combining this with (3.7) completes the proof.

Proposition 3.10. Let a_{1}, …, a_{n} be non-negative real numbers and R > 0. Let m be the number of the a_{k}’s that satisfy a_{k} > π/(2R). By reordering it can be assume that a_{k} ≤ π/(2R) for k ≤ (n − m) and a_{k} > π/(2R) for k ≥ (n − m + 1). Then

∫_{−R}^{R} ∏_{k=1}^{n} | cos(a_{k}x + b_{k})| dx ≤ \begin{matrix}√ & \overline{2π} \\ √ & \overline{(mπ^{2})/(16R^{2}) + ∑_{k=1}^{n−m} a_{k}^{2}} \end{matrix} .

Thus

∫_{−R}^{R} ∏_{k=1}^{n} | cos(a_{k}x + b_{k})| dx ≤ \begin{matrix}√ & \overline{2π} \\ √ & \overline{(mπ^{2})/(16R^{2})} \end{matrix} = \frac{8R}{\sqrt{2πm}}

and

∫_{−R}^{R} ∏_{k=1}^{n} | cos(a_{k}x + b_{k})| dx ≤ \begin{matrix}√ & \overline{2π} \\ √ & \overline{∑_{k=1}^{n−m} a_{k}^{2}} \end{matrix} .

Proof. From the rearrangement Theorem 3.1 and Lemmas 3.4 and 3.5 which give explicit bounds on the symmetric rearrangements of the functions f_{k}(x) = | cos(a_{k}x + b_{k})| we have

∫_{−R}^{R} ∏_{k=1}^{n} | cos(a_{k}x + b_{k})| dx ≤ ∫_{−R}^{R} cos^{m}(πx/(4R)) ∏_{k=1}^{n−m} cos(a_{k}x) dx.

Now use the inequality

cos(x) ≤ e^{−x^{2}/2} for |x| ≤ π/2

of Lemma 3.6 to estimate

∫_{−R}^{R} cos^{m}(πx/(4R)) ∏_{k=1}^{n−m} cos(a_{k}x) dx ≤ ∫_{−∞}^{∞} e^{− \frac{1}{2} ( \frac{mπ^{2}}{16R^{2}} +∑_{k=1}^{n−m} a_{k}^{2})x^{2}}dx

= \begin{matrix}√ & \overline{2π} \\ √ & \overline{(mπ^{2})/(16R^{2}) + ∑_{k=1}^{n−m} a_{k}^{2}} \end{matrix} .

Putting these inequalities together completes the proof.

4. Estimates on the concentration.

4.1. A one dimensional result.

Theorem 4.1. Let a_{1}, …, a_{n} be real numbers and let m be the number of the a_{k}’s that satisfy |a_{k}| > 1 and ordered so that |a_{k}| ≥ 1 for k > n − m. Then

N_{[−1,1]} ≤ \frac{π\sqrt{2π}}{2\sqrt{m + 4 ∑_{k=1}^{n−m} a_{k}^{2}}} 2^{n} ≤ \frac{3.94}{\sqrt{m + 4 ∑_{k=1}^{n−m} a_{k}^{2}}} 2^{n}.

Thus

N_{[−1,1]} ≤ \frac{π\sqrt{2π}}{2\sqrt{m}} 2^{n} ≤ \frac{3.94}{\sqrt{m}} 2^{n}

and

N_{[−1,1]} ≤ \frac{π\sqrt{2π}}{4\sqrt{∑_{k=1}^{n−m} a_{k}^{2}}} 2^{n} ≤ \frac{1.97}{\sqrt{∑_{k=1}^{n−m} a_{k}^{2}}} 2^{n}.

Proof. Replacing a_{k} by −a_{k} does not change the value of N_{[−1,1]} and so there is no loss in generality by assuming that a_{k} ≥ 0 for all k. Letting r = 2 and d = 1 in Proposition 2.6 gives

N_{[−1,1]} ≤ 2^{n} \frac{2π}{8} ∫_{−π/2}^{π/2} ∏_{k=1}^{n} | cos(a_{k}x)| dx.

Now in Proposition 3.10 let R = π/2. Then π/(2R) = 1 and by assumption there are exactly m of the a_{k}’s with a_{k} ≥ 1 = π/(2R). Therefore Proposition 3.10 yields

∫_{−π/2}^{π/2} ∏_{k=1}^{n} | cos(a_{k}x)| dx ≤ \begin{matrix}√ & \overline{2π} \\ √ & \overline{(mπ^{2})/(16R^{2}) + ∑_{k=1}^{n−m} a_{k}^{2}} \end{matrix} = \begin{matrix}√ & \overline{2π} \\ √ & \overline{m/4 + ∑_{k=1}^{n−m} a_{k}^{2}} \end{matrix} .

Putting these estimates together gives the result.

4.2. Estimates when a positive proportion of the vectors have at least unit length.

Theorem 4.2. Let v_{1}, , …, v_{n} ∈ R^{d} and assume that there is a number δ > 0 so that at least δn of the vectors v_{k} satisfy |v_{k}| ≥ 1. Then if r ≤ 2/\sqrt{d}

N_{Q(r)} ≤ C_{1}(d)\frac{1}{\sqrt{δn}}2^{n}

where

C_{1}(d) ≤ 4(2π)^{d−1/2} (\frac{π}{8} )^{d} .

Proof. Let v_{k} = (v_{1}^{(k)}, …, v_{d}^{(k)}). Then if |v_{k}| ≥ 1 for at least one index j the inequality |v_{j}^{(k)}| ≥ 1/\sqrt{d} holds. Therefore the hypothesis of the theorem

implies that at least δn of the vectors v_{k} will have |v_{j}^{(k)}| ≥ 1/\sqrt{d}. But then there will be a fixed j_{0} so that at least δn/d of the vectors will have |v_{j_{0}}^{(k)}| ≥ 1/\sqrt{d}. By relabeling we can assume that j_{0} = 1 and that for some

m ≥ δn/d that |v_{1}^{(k)}| ≥ 1/\sqrt{d}. To simplify notation let a_{k} := v_{1}^{(k)} for k = 1, …, m (so that |a_{k}| ≥ 1/\sqrt{d}). Write vectors ξ ∈ R^{d} and ξ = (t, ξ′) where t = ξ_{1} is the first coordinate of ξ and ξ′ = (ξ_{1}, …, ξ_{d}). With this notation for 1 ≤ k ≤ m we have ⟨v^{k}, ξ⟩ = a_{k}t + b_{k} where b_{k} = ⟨v′_{k}, ξ′⟩ (so that b_{k} is independent of t = ξ_{1}). Therefore

∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| ≤ ∏_{k=1}^{m} | cos(a_{k}t + b_{k})|.

Let Q′(2π/r) be the centered cube in R^{d−1} with edges of length 2π/r so that Q′(2π/r) = [−π/r, π/r] × Q′(2π/r). Using this estimate by integrating one coordinate at a time

∫_{Q(2π/r)} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ ≤ ∫_{Q′(2π/r)} ∫_{−π/r}^{π/r} ∏_{k=1}^{m} | cos(a_{k}t + b_{k})| dt dξ′

= Vol(Q′(2π/r)) ∫_{−π/r}^{π/r} ∏_{k=1}^{m} | cos(a_{k}t + b_{k})| dt

= (\frac{2π}{r} )^{d−1} ∫_{−π/r}^{π/r} ∏_{k=1}^{m} | cos(a_{k}t + b_{k})| dt.

If R = π/r then π/(2R) = r/2 ≤ 1/\sqrt{d} ≤ |a_{k}| and so by Proposition 3.10 the estimate

∫_{−π/r}^{π/r} ∏_{k=1}^{m} | cos(a_{k}t + b_{k})| dt ≤ \frac{8R}{\sqrt{2πm}} = \frac{4\sqrt{2π}}{\sqrt{m}r} ≤ \frac{4\sqrt{2π}}{\sqrt{δn}r}

holds (and we have used m ≥ δn). Combining with the above we have

∫_{Q(2π/r)} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ ≤ \frac{4(2π)^{d−1/2}}{\sqrt{δn}} (\frac{1}{r})^{d} .

Combining this with Proposition 2.6 completes the proof.

4.3. Estimates when the many of the vectors are not all close to a hyperplane. The following is a very slight generalization of Theorem 1 of Halász’s paper [2].

Theorem 4.3. Let v_{1}, …, v_{n} ∈ R^{d} and assume that for any unit vector u that there are at least m indices k so that |⟨v_{k}, u⟩| ≥ 1. Then

N_{Q(2\sqrt{d})} ≤ C_{2}(d) (\frac{1}{\sqrt{m}})^{d} 2^{n}.

where

C_{2}(d) ≤ (\frac{π^{2}d}{\sqrt{2π}} )^{d} .

In particular this implies that if for some δ ∈ (0, 1) that m ≥ δn then

N_{Q(2\sqrt{d})} ≤ C_{2}(d) (\frac{1}{\sqrt{δn}})^{d} 2^{n}.

Proof. Let r = 2\sqrt{d} in Proposition 2.6 to get

N_{Q(2\sqrt{d})} ≤ 2^{n} (\frac{π\sqrt{d}}{4})^{d} ∫_{Q(π/\sqrt{d})} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ.

Let 2R = π/\sqrt{d} om Proposition 3.9 to get

∫_{Q(π/\sqrt{d})} ∏_{k=1}^{n} | cos⟨v_{k}, ξ⟩| dξ ≤ (\frac{4\sqrt{d}π}{\sqrt{2π}} )^{d} (\frac{1}{\sqrt{m}})^{d} .

Putting these two estimates together completes the proof.

References

1. Jerry Griggs, Oral Commutation, September 1997.

2. G. Halász, Estimates for the concentration function of combinatorial number theory and probability, Period. Math. Hungar. 8 (1977), no. 3-4, 197–211.

3. Elliott H. Lieb and Michael Loss, Analysis, Graduate Studies in Mathematics, vol. 14, American Mathematical Society, Providence, RI, 1997.