New bounds on the dimensions of planar distance sets
Tamás Keleti Pablo Shmerkin
math.CA math.CO math.MG 28A75, 28A80 (Primary) 26A16, 49Q15 (Secondary)



We prove new bounds on the dimensions of distance sets and pinned distance sets of planar sets. Among other results, we show that if A⊂^2 is a Borel set of Hausdorff dimension s>1, then its distance set has Hausdorff dimension at least 37/54≈ 0.685. Moreover, if s∈ (1,3/2], then outside of a set of exceptional y of Hausdorff dimension at most 1, the pinned distance set { |x-y|:x∈ A} has Hausdorff dimension ≥23s and packing dimension at least 14(1+s+√(3s(2-s))) ≥ 0.933. These estimates improve upon the existing ones by Bourgain, Wolff, Peres-Schlag and Iosevich-Liu for sets of Hausdorff dimension >1. Our proof uses a multi-scale decomposition of measures in which, unlike previous works,  we are able to choose the scales subject to certain constrains. This leads to a combinatorial problem,  which is a key new ingredient of our approach, and which we solve completely by optimizing certain variation of Lipschitz functions.



The Near-Infrared Outflow and Cavity of the proto-Brown Dwarf Candidate ISO-Oph 200Based on Observations collected with SINFONI at the Very Large Telescope on Cerro Paranal (Chile), 
operated by the European Southern Observatory (ESO). Program ID: 097.C-0732(A).
    Whelan, E.T. 1
  Riaz, B. 2
   Rouzé, B. 1
    
======================================================================================================================================================================================================================================================================








§ INTRODUCTION AND STATEMENT OF RESULTS




 §.§ Introduction


Given A⊂^d, its distance set is Δ(A)={|x-y|:x,y∈ A}. K. Falconer <cit.> pioneered the study of the relationship between the Hausdorff dimensions of A and Δ(A). He proved that if d≥ 2 and A⊂^d is a Borel (or even analytic) set then (Δ(A)) ≥min((A)-12(d-1),1), where  stands for Hausdorff dimension. Falconer also constructed compact sets A⊂^d (based on lattices) of any Hausdorff dimension such that (Δ(A)) ≤min(2(A)/d,1). Although it is not explicitly stated in <cit.>, the conjecture that these lattice constructions are extremal, in the sense that one should have (Δ(A))=1 if (A)≥ d/2, has become known as the Falconer distance set problem.

Falconer's problem is a continuous version of the celebrated P. Erdős distinct distances problem <cit.>, asserting (in the plane) that if |A|=N, A⊂^2, then |Δ(A)|≥ c N/√(log N). L. Guth and N. Katz <cit.> (building up on work of Gy. Elekes and M. Sharir <cit.>) famously solved this problem, up to logarithmic factors, by showing that |Δ(A)| ≥ c N/log N. However, the approach of Guth and Katz and, indeed, all previous methods developed to tackle Erdős' problem, do not appear to be able to yield progress on Falconer's problem.

From now on, we focus on the case d=2, which is the first non-trivial case,  the best understood, and the focus of this article. T. Wolff <cit.>, based on a method of P. Mattila <cit.> and extending ideas of J. Bourgain <cit.>, proved that if A⊂^2 is a Borel set with (A)≥ 4/3, then (Δ(A))=1. In fact, he proved that (A)>4/3 ensures that Δ(A) has positive length, and established the more general dimension formula

    (Δ(A)) ≥min( 3/2(A)-1,1),

whenever (A)>1. The method developed by Mattila and Wolff is strongly Fourier-analytic, depending on difficult estimates for the decay of circular averages of the Fourier transform of measures.

Later Bourgain <cit.>, crucially relying on earlier work of N. Katz and T. Tao <cit.>, proved that if A⊂^2 satisfies (A)≥ 1, then

    (Δ(A)) > 1/2 + δ,

where δ>0 is a universal constant. Although non-explicit, it is clear from the proof that the value of δ one would get is extremely small. The method of Katz-Tao and Bourgain is based on additive combinatorics, and it seems difficult for this type of arguments to yield reasonable values of δ.

A related problem concerns the dimensions of pinned distance sets

    Δ_y(A) = { |x-y|:x∈ A}.

Y. Peres and W. Schlag <cit.> proved that if A⊂^2 is a Borel set with (A)=s, then for all 0<t≤min(s,1),

    { y∈^2: (Δ_y(A)) < t }≤ 2+t-max(s,1).

Recently, A. Iosevich and B. Liu <cit.> proved that (<ref>) remains true with 3+3t-3s in the right-hand side. This is an improvement in some parts of the parameter region. Both results imply that if (A)>3/2, then there is y∈ A such that (Δ_y A)=1, and it is unknown whether 3/2 can be replaced by a smaller number. We remark that the results of both <cit.> and <cit.> extend to higher dimensions.

These were the best known results towards Falconer's problem in the plane for general sets prior to this article. For some special classes of sets, better results are known. In particular, the second author proved in <cit.> that if A⊂^2 is a Borel set of equal Hausdorff and packing dimension, and this value is >1, then (Δ_y(A))=1 for all y outside of a set of exceptions of Hausdorff dimension at most 1, and in particular for many y∈ A. This verifies Falconer's conjecture for this type of sets, outside of the endpoint. We remark that T. Orponen <cit.> and the second author <cit.> had previously proved weaker results of the same kind. See also <cit.> for other results on the distance sets of special classes of sets.



 §.§ Main results


In this article we prove new lower bounds on the dimensions of (pinned) distance sets, which in particular greatly improve the best previously known estimates when (A)=1+δ, δ>0 small.

 
If A is a Borel subset of ^2 with A=s, then

    { y∈^2: (Δ_y(A)) <  min(2/3s,1) }≤max(1,2-s).

In particular, if s>1, then one can find many y∈ A such that

    (Δ_y(A)) ≥min(2/3s,1).



We remark that we get better bounds for the dimension of the full distance set, see Theorem <ref> below.

The last claim in Theorem <ref> improves the previously known bounds for the dimensions of pinned distance sets Δ_y(A) with y∈ A for all s∈ (1,3/2].  The bound (<ref>)  also improves upon (<ref>) (and the variant of Iosevich and Liu) in large regions of parameter space, and in particular for   t=min(23s,1) and all s∈ (3/5,5/3).

Theorem <ref> is a special case of a more general result that takes into account the Hausdorff and also the packing dimension of A. We refer to <cit.> for the definition and main properties of packing dimension , and simply note that it satisfies (A)≤(A)≤(A), where  denotes the upper box-counting (or Minkowski) dimension.  For our method, the worst case is that in which A has maximal packing dimension 2, and we get better bounds for the distance set under the assumption that the packing dimension is smaller:

 
Let

    χ(s,u) = s(2+u-2s)/2+2u-3s    if  u>2s-1
    
    1     if  u≤ 2s-1
    .


Given 0< s≤ u ≤ 2, the following holds: if A is a Borel subset of ^2 with A≥ s and A ≤ u, then

    { y∈^2: (Δ_y(A)) <  χ(s,u)  }≤max(1,2-s).

In particular, if s>1 then there are many y∈ A such that

    (Δ_y(A)) ≥χ(s,u),

and hence if (A)>1 and A≤ 2 A-1, then (Δ_y(A))=1 for many y∈ A.


Note that Theorem <ref> follows immediately by taking u=2.  A simple calculation shows that if 0≤ s≤ u ≤ 2 and s<2, then

    χ(s,u) = min(s(2+u-2s)/2+2u-3s,1).

We remark that, taking u=s, this theorem recovers the main result of <cit.> mentioned above, namely that if (A)=(A)>1, then (Δ_y A)=1 for many y∈ A. On the other hand, it was known from (<ref>) that if (A)>3/2 then there is y∈ A such that (Δ_y A)=1. The last claim in Theorem <ref> can be seen as interpolating between these two situations, and hence provides a new, more general, geometric condition under which Falconer's conjecture is known to hold.


When (A)>1, we are able to get much better lower bounds for the packing dimension of the pinned distance sets:
 
Let A be a Borel subset of ^2 with s=(A)∈ (1,3/2). Then

    { y∈^2: (Δ_y(A)) < 1+s+√(3s(2-s))/4}≤ 1.

In particular, there is y∈ A such that

    (Δ_y(A)) ≥1+s+√(3s(2-s))/4 > 2+√(3)/4 =  0.933013….



We recall that since upper box-counting dimension is at least as large as packing dimension, the above theorem also holds for upper box-counting dimension. Even though Falconer's conjecture is about the Hausdorff dimension of the distance set, this result presents further evidence towards its validity.




Finally, as anticipated above, we get a better bound for the dimension of the full distance set when (A) is slightly larger than 1:
  
If A^2 is a Borel set with (A)=s∈ (1,4/3), then

    (Δ(A))≥s(147-170s+60s^2)/18(12-14s+5s^2)≥37/54=0.6851851….






A calculation shows that this indeed improves upon Wolff's bound (<ref>) for the dimension of the full distance set for s∈ (1,1.21931…) (and upon Bourgain's bound (<ref>)  for all s>1). We remark that this theorem is obtained by combining the idea of the proof of Theorem <ref> with a known effective variant of Wolff's bound (<ref>). Although achieving this combination takes quite a bit of work, Theorem <ref> should perhaps be considered the most basic result, since its proof is shorter and already contains most of the main ideas, and the improvement given by Theorem <ref> is relatively modest. Note also that already applying Theorem <ref> for the full distance set improves upon (<ref>) for s∈ (1,6/5). See Figure <ref> for a comparison of the lower bounds from Theorems <ref>, <ref> and <ref> and Wolff's lower bound.

After this paper was made public, B. Liu <cit.> posted a preprint extending Wolff's result to pinned distance sets. In particular, he shows that if A⊂^2 is a Borel set with (A)>4/3, then Δ_x(A) has positive Lebesgue measure for some x∈ A (with bounds on the dimension of the exceptional set). This is stronger than our Theorem <ref> for s>4/3 (other than the exceptional set being larger).



 §.§ Strategy of proof


Our approach is completely different to those of Wolff, Bourgain, Peres and Schlag and Iosevich and Liu. Rather, it can be seen as a continuation of the ideas successively developed in <cit.> to attack the distance set problems for sets with certain regularity. Thus, one of the main points of this paper is extending the strategy of these papers so that it can be applied to general sets.

At the core of our method is a lower box-counting estimate for pinned distance sets Δ_y A in terms of a multi-scale decomposition of A or, rather, a Frostman measure μ supported on A. See Section <ref> for precise statements. A key aspect of these estimates is that they recover a global lower box-counting estimate for Δ_y A from bounds on local, discretized and linearized estimates for the pinned distance measures Δ_y μ.

The general philosophy of obtaining lower bounds for the dimension of projected sets and measures, in terms of multi-scale averages of local projections is behind a large number of results in fractal geometry in the last few years, see e.g. <cit.> and references there. The insight that this approach can be used also to study distance sets is due to Orponen <cit.>.

Up until the paper <cit.>, the scales in the multi-scale decomposition behind all the variants of the method described above were of the form 2^-N j for some fixed N. One of the innovations of <cit.> was to modify the method so that it could handle also scales of the form 2^-(1+)^j (the point being that (1+)^j is exponential in j, rather than linear). Although this was flexible enough to handle sets of equal Hausdorff and packing dimension (as opposed to Ahlfors-regular sets as in <cit.>), it was still too restrictive for dealing with general sets.

One of the main innovations of this paper is that we are able to work with scales 2^-M_j where the M_j only need to satisfy τ M_j ≤ M_j+1-M_j≤ M_j+T (where τ>0, T∈ are fixed parameters). This provides a major degree of flexibility. In particular, a crucial point is that we are able to pick the sequence (M_j) depending on the set A (or the Frostman measure μ), while in all previous works the scales in the multi-scale decomposition were basically fixed. See Proposition <ref>. This leads us to the combinatorial problem of optimizing the choice of (M_j) for each measure μ. We solve this problem completely, up to negligible error terms, in Section <ref>.

In fact, we deduce the combinatorial statements we need from several statements about the variation of Lipschitz functions, which might be of independent interest. More precisely, given a 1-Lipschitz function f:[0,a]→ satisfying certain additional assumptions, we seek to minimize

    ∑_n=1^∞ f(a_n)-min_[a_n,a_n-1] f,

where (a_n)_n=0^∞ is a strictly decreasing sequence tending to 0 with a=a_0 and a_n≤ 2 a_n+1. Conversely, we also study the structure of functions f for which these sums are (for some sequence (a_i)) close to the minimum possible value. We underline that this part of the method is completely new as the combinatorial problem does not arise for fixed multi-scale decompositions.

Another obstacle to dealing with arbitrary sets and measures is that energies of measures (which play a key role throughout) do not have a nice multi-scale decomposition in general. We deal with this by decomposing a general measure supported on [0,1)^2 as a superposition of measures with a regular Cantor structure, plus a small error term: see Corollary <ref>. This step is an adaptation of some ideas of Bourgain we learned from <cit.>. After some technical difficulties, this reduces our study to those regular measures for which a suitable multi-scale expression of the energy does exist, see Lemma <ref>.

The strategy just discussed is behind the proofs of Theorems <ref>, <ref> and <ref>. However (as briefly indicated above), the proof of Theorem <ref> is based on merging these ideas with a more quantitative version of Wolff's result that if (A)≥ 4/3 then (Δ(A))=1, see Theorem <ref> below. The fact that one can improve upon Theorem <ref> (for the full distance set) is based on the observation that for some sets A⊂^2 of Hausdorff dimension s>1 for which the method of the proof of Theorem <ref> cannot give anything better than (Δ(A))≥ 2s/3, the quantitative version of Wolff's Theorem can give a much better bound. The fact that these two methods are based on totally different techniques and also have different “enemies” that one must overcome, suggests that neither of them (or even in combination as we do here) provides a definitive line of attack on Falconer's problem.



 §.§ Sets of directions, and the case of dimension 1


Although Theorem <ref> does provide new information on the pinned distance sets Δ_y A when A=1, it gives no information whatsoever on (Δ(A)) in this case. There are some well-known “enemies” that one must handle in order to improve upon the easy bound (Δ(A))≥ 1/2 when A=1. One is that the corresponding fact is false over the complex numbers: ^2 is a subset of ℂ^2 of half the dimension of the ambient space for which the (squared) distance set

    Δ^2(^2) = { (x_1-y_1)^2 + (x_2-y_2)^2 : (x_1,x_2), (y_1,y_2)∈^2}

also has half the dimension of the ambient space. Hence any improvements over 1/2 in the real case must take into account the order structure of . The other obstacle is a well-known counterexample to a naive discretization of the problem: see <cit.>. These enemies do not arise when (A)>1. Despite these conceptual differences, we underline that, with the exception of the work of Katz and Tao <cit.> underpinning Bourgain's bound (<ref>), none of the other methods developed so far make any distinction between the cases (A)=1 and (A)=1+δ.

From the point of view of our strategy, the key significance of the assumption (A)>1 is that in this case the sets of directions determined by points in A has positive Lebesgue measure. In fact, we need a far more quantitative “pinned” version of this fact, which is due to Orponen <cit.>, improving upon a related result by Mattila and Orponen <cit.> (see Proposition <ref> below). However, even the fact that the direction set has positive measure clearly fails if A=1 when A is contained in a line. Since (Δ_y A) = (A) trivially when A is contained in a line, this does not rule out an extension of our approach to the case (A)=1. However, this would require some variant of Proposition <ref> when both s,u are slightly less than 1, under a suitable hypothesis of non-concentration on lines, and this appears to be very hard. In <cit.>, Orponen also proved that the direction set of a planar set of Hausdorff dimension 1 which is not contained in a line has Hausdorff dimension ≥ 1/2, but this is very far from positive measure, let alone from anything resembling Proposition <ref>.

To understand why directions arise naturally, we recall that our whole approach is based on bounding the size of pinned distance sets in terms of a multi-scale average of local linearized pinned distance measures. The derivative of the distance function x↦ |x-y| is precisely the direction spanned by x and y. Thus we are led to study orthogonal projections of certain measures localized around x, where the angle is given by the direction determined by x and y. The fact that these directions are “well distributed” in a suitable sense can then be used in conjunction with a finitary version of Marstrand's projection theorem (see Lemma <ref>) and several applications of Fubini to conclude that one can choose y such that for “many” x the direction determined by x and y is good in the sense that the L^2 norm of the projection is controlled by the 1-energy of the measure being projected.



 §.§ Structure of the paper
 In Section <ref> we introduce notation to be used in the rest of the paper. Section <ref> contains some preliminary definitions and results that will be repeatedly used in the later proofs. In Section <ref> we establish a lower bound for the box-counting numbers of pinned distance sets that will be at the heart of the proofs of all main theorems. Section <ref> contains a number of optimization results about Lipschitz functions on the line, as well as corollaries of these results for discrete [-1,1]-sequences; these corollaries play a key role in the proofs of the main theorems. Theorems <ref>, <ref> and <ref> are proved in Section <ref>. We conclude with some remarks on the sharpness of our results in Section <ref>.

We remark that <ref> and <ref> are not needed for the proof of Theorem <ref> (the results from <ref> are required only in the proof of Theorem <ref>, and <ref>  is needed only for the proof of Theorem <ref>).



 §.§ Acknowledgments
 This project was started while the authors were staying at Institut Mittag-Leffler as part of the program Fractal Geometry and Dynamics. We are grateful to the organizers for the opportunity to take part, and to the organizers, staff, and fellow participants for the pleasant stay.

We also wish to thank for T. Orponen for many useful discussions at the early stage of this project, and an anonymous referee for several suggestions that improved the paper, and in particular for suggesting a simplification of the statement and proof of Proposition <ref>.




§ NOTATION



We use Landau's O(·) notation: given X>0, O(X) denotes a positive quantity bounded above by C X for some constant C>0. If C is allowed to depend on some other parameters, these are denoted by subscripts. We sometimes write X≲ Y in place of X=O(Y) and likewise with subscripts. We write X≳ Y,  X≈ Y to denote Y≲ X,  X≲ Y≲ X respectively.

Throughout the rest of the paper, we work with three parameters that we assume fixed: a large integer T and small positive numbers ,τ. We briefly indicate their meaning:


  * We will decompose sets and measures in the base 2^T. In particular, we will work with sets and measures that have a regular tree (or Cantor) structure when represented in this base: see Definition <ref>.

  * The parameter τ will be used to define sets of bad projections: see Definition <ref>. The fact that τ>0 is required to ensure that these sets have small measure. It also keeps some error terms negligible, see Proposition <ref>.

  * Finally,  will denote a generic small parameter; it can play different roles at different places.


We will use the notation  o_T,,τ(1)=o_T→∞,→ 0^+,τ→ 0^+(1) to denote any function f(T,,τ) such that

    f(T,,τ)≥ 0   and  lim_T→∞,→ 0^+,τ→ 0^+ f(T,,τ)=0.

If a particular instance of o(1) is independent of some of the variables, we drop these variables from the notation.  Different instances of the o(1) notation may refer to different functions of T,,τ, and they may depend on each other, so long as they can always be made arbitrarily small.

Note that e.g. O_(1) denotes any (finite) function of , while o_(1) denotes a function of  that tends to 0 as → 0^+.

We will often work at a scale 2^-Tℓ;  it is useful to think that ℓ→∞ while T,,τ remain fixed.

The family of Borel probability measures on a metric space X is denoted by (X). If μ(A)>0, then μ_A denotes the normalized restriction μ(A)^-1μ|_A. If f:X→ Y is a Borel map, then by fμ we denote the push-forward measure, i.e. fμ(A)= μ(f^-1A).

We let _j be the half-open 2^-jT-dyadic cubes in ^d (where d is understood from context), and let _j(x) be the only cube in _j containing x∈^d. Given a measure μ∈(^d), we also let _j(μ) be the cubes in _j with positive μ-measure. Note that these families depend on T. Given A⊂^d, we also denote by (A,j) the number of cubes in _j that intersect A.

A 2^-m-measure is a measure in ([0,1)^d) such that the restriction to any 2^-m-dyadic cube Q is a multiple of Lebesgue measure on Q, i.e. a measure defined down to resolution 2^-m. Likewise, a 2^-m-set is a union of 2^-m dyadic cubes. If μ∈(^d) is an arbitrary measure, then we denote

    R_ℓ(μ) = ∑_Q∈_ℓμ(Q) Leb_Q,

that is R_ℓ(μ) is the 2^-Tℓ-measure that agrees with μ on all dyadic cubes of side length 2^-Tℓ. We also define the corresponding analog for sets:  given A⊂^d, R_ℓ(A) denotes the union of all cubes in _ℓ that intersect A.

Due to our use of dyadic cubes,  it will often  be convenient to deal with supports in the dyadic metric, i.e. given μ∈([0,1)^d) we let

    _𝖽(μ) = { x: μ(_j(x))>0  for all  j∈}.

Note that μ(_𝖽(μ))=1 and that _𝖽(μ)⊂(μ).

If a measure μ∈(^d) has a density in L^p, then its density is sometimes also denoted by μ, and in particular  μ_p stands for the L^p norm of its density.

We make some further definitions. Let μ∈([0,1)^d). If Q is a dyadic cube and μ(Q)>0, then we denote μ^Q = Hom_Qμ_Q, where  Hom_Q is the homothety renormalizing Q to [0,1)^d. If M<N be integers, then for x∈_𝖽(μ), we define

    μ(x;M  N) = R_N-Mμ^_M(x).

In other words, μ(x;M N) is the conditional measure on _M(x), rescaled back to the unit cube, and then stopped at resolution 2^-(N-M)T.  Likewise, for Q∈_M with μ(Q)>0 we define

    μ(Q;N) = R_N-Mμ^Q.

Note that μ(x;M N) and μ(Q;N) are 2^-(N-M)T-measures.

Logarithms are always to base 2.



§ PRELIMINARY RESULTS





 §.§ Regular measures and energy



In this section we define some important notions and prove some preliminary results.

Recall that the s-energy of μ∈(^d) is

    _s(μ) = ∬dμ(x)dμ(y)/|x-y|^s.



 
For any Borel probability measure μ on [0,1]^d, if s>0 then

    _s(μ) ≈_s,d,T∑_j=1^∞ 2^s T j∑_Q∈_jμ(Q)^2.

If μ is a 2^-Tℓ-measure and 0<s<d, then the sum runs up to ℓ (in particular, the s-energy is finite).


First of all, by <cit.>, we can replace _s(μ) by the s-energy on the 2^T-ary tree, i.e. by

    ∬ 2^s T|x∧ y| dμ(x)dμ(y),

where |x∧ y| = max{ j: y∈_j(x)} (both energies are comparable up to a O_T,d(1) factor). The formula for _s(μ) now follows from a standard calculation, see e.g. <cit.> for the case T=1 (the proof of the general case is identical).

Finally, the case in which μ is a 2^-Tℓ-measure follows again from another simple calculation, see e.g. <cit.> for the case T=1.


One of the key steps in the proof of the main theorems is to decompose an arbitrary 2^-Tℓ-measure in terms of measures which have a uniform tree structure when represented in base 2^T. This notion (which is inspired by some constructions of Bourgain <cit.>) is made precise in the next definition.

 
Given a sequence σ=(σ_1,…,σ_ℓ)∈ [-1,d-1]^ℓ, we say that μ∈([0,1)^d) is σ-regular if it is a 2^-Tℓ-measure, and for any Q∈_j(μ), 1≤ j≤ℓ, we have

    μ(Q) ≤ 2^-T(σ_j+1)μ(Q) ≤ 2μ(Q),

where Q is the only cube in _j-1 containing Q.

The expression 2^-T(σ_j+1) in the definition may appear strange, but it turns out to be a convenient normalization. The key point in this definition is that a measure is σ-regular if all cubes of positive mass have roughly the same mass, and the sequence (σ_j) helps quantify this common mass.

 
If ν∈([0,1)^d) is σ-regular for some σ∈^ℓ and s∈ (0,d), then

    |log_s(ν)-( T max_j=0^ℓ∑_i=1^j (s-1)-σ_i )|≤ O(ℓ) + O_d,s,T(1).



We use crude bounds which are enough for our purposes. From the definition it is clear that if Q∈_j(ν) then

    2^-ℓ 2^-T(σ_1+1)⋯ 2^-T(σ_j+1)≤ 2^-j 2^-T(σ_1+1)⋯ 2^-T(σ_j+1)≤ν(Q) ≤ 2^-T(σ_1+1)⋯ 2^-T(σ_j+1) .

This implies, in particular, that

    2^T(σ_1+1)⋯ 2^T(σ_j+1)≤ |_j(ν)|≤ 2^ℓ 2^T(σ_1+1)⋯ 2^T(σ_j+1) .

From the two displayed equations and  Lemma <ref> it follows that

    2^-2ℓ∑_j=1^ℓ 2^-T(σ_1+…+σ_j+j)·  2^s T j≲_d,s,T_s(ν) ≲_d,s,T 2^ℓ∑_j=1^ℓ  2^-T(σ_1+…+σ_j+j)· 2^sTj.

Write ℳ_s(σ) := T max_j=1^ℓ∑_i=1^j (s-1)-σ_j. Bounding  ∑_j=1^ℓ by ℓ times the maximal term in the right-hand side, we deduce that

    ℳ_s(σ) -2ℓ-O_d,s,T(1) ≤log_s(ν) ≤ℳ_s(σ) + ℓ +logℓ +O_d,s,T(1).

This yields the claim.

Heuristically, the previous lemma says that for log_s(ν) to be small, it must hold that

    ∑_i=1^j σ_i ≥ (s-1)j,    j=0,…,ℓ.

Recalling the connection of σ_i to branching numbers, this means that the average branching number over any initial set of scales has to be sufficiently large, in a manner depending on s.

The following is a variant of Bourgain's regularization argument (see e.g. <cit.> for a clean example). Recall that  _𝖽(μ) denotes the dyadic support of μ.
 
Let μ be a 2^-Tℓ-measure on [0,1)^d for some ℓ≥ 1. There exists a 2^-Tℓ-set X, contained in _𝖽(μ) and satisfying μ(X) ≥ (2Td+2)^-ℓ, such that μ_X is σ-regular for some sequence σ∈ [-1,d-1]^ℓ.


Recall that Q is the only cube in _j-1 containing Q∈_j. For each k∈ [0,Td]∩, let

    X_ℓ^(k) = ⋃{ Q∈_ℓ:   μ(Q) ≤  2^-kμ(Q) < 2μ(Q) },

and set

    X_ℓ^(>Td) = ⋃{ Q∈_ℓ:   μ(Q) ≤  2^-(Td+1)μ(Q)  }.

Note that

    μ(X_ℓ^(>Td)) ≤ 2^-(Td+1) 2^Td = 1/2,

and that _𝖽(μ) is the union of the X_ℓ^(k) together with X_ℓ^(>Td). Pick the smallest k=k(ℓ)∈ [0,Td] which maximizes μ(X_ℓ^(k)) and set σ_ℓ = k/T-1∈ [-1,d-1]. Then

    μ(X_ℓ^(k)) ≥1/2(Td+1) .

Set X_ℓ:= X_ℓ^(k) and μ_ℓ=μ_X_ℓ.

Now continue inductively, replacing ℓ by ℓ-1 and μ by μ_ℓ, until we eventually get a set X_1 and a sequence (σ_1,…,σ_ℓ)∈ [-1,d-1]^ℓ. Note that for Q∈_j(μ_i) the value of μ_i(Q)/μ_i(Q) remains constant for i≤ j and, in particular, for i=1. Hence X=X_1 has the desired properties.


The set X given by the lemma will have far too little measure for our purposes: later we will need μ_X(A) to be large (in particular nonzero) for certain sets A of mass roughly ℓ^-2. By iterating the construction, we are able to get a moderately long sequence of sets X_i such that μ(^d∖∪_i X_i)≪ℓ^-2; by pigeonholing we will then be able to select some X_i with μ_X_i(A) suitably large.
 
Fix ℓ≥ 1, write m=Tℓ, and let μ be a 2^-m-measure on [0,1)^d.  There exists a family of pairwise disjoint 2^-m-sets X_1,…, X_N  with X_i⊂_𝖽(μ), and such that:


  * μ(⋃_i=1^N X_i) ≥ 1-2^- m. In particular, if μ(A)> 2^- m, then there exists i such that μ_X_i(A)≥μ(A)-2^- m.

  * μ(X_i) ≥ 2^-(+(1/T)log(2d T+2)) m≥ 2^-o_T,(1) m,

  * Each μ_X_i is σ(i)-regular for some σ(i)∈  [-1,d-1]^ℓ.

Moreover, the family (X_i)_i=1^N may be constructed so that it is determined by d, T,,ℓ and μ (even though there may be other families satisfying the above properties).


Let X_1 be the set given by Lemma <ref>, and put B_1=[0,1]^d∖ X_1. Continue inductively: once X_j,B_j are defined, let X_j+1 be the set given by  Lemma <ref> applied to μ_B_j, and set B_j+1=B_j∖ X_j+1. Then (setting B_0=[0,1)^d)

    μ(B_j) ≥ 2^- m  ⟹  μ(X_j+1) ≥ 2^- m (2d T+2)^-ℓ.

Let N be the smallest integer such that μ(B_N) ≤  2^- m; such N exists thanks to (<ref>).

It is clear that in this construction the family X_1,…,X_N is determined by d,T,,ℓ,μ since the set X constructed in the proof of Lemma <ref> is determined by d,T,ℓ,μ.

The first part of claim (i) is immediate. Then note that

    μ(A)-2^- m≤∑_i=1^N μ(X_i ∩ A) = ∑_i=1^N μ(X_i) μ_X_i(A),

so there must be i such that μ_X_i(A) ≥μ(A)-2^- m, as claimed.

Finally, (ii) is immediate from (<ref>) and the definition of N, and (iii) is clear since the sets X_i were provided by Lemma <ref>.





 §.§ Sets of bad projections



In this subsection, we introduce sets of “bad” multi-scale projections for a measure μ around a point x. The simple fact that these sets can be taken to have small measure (independently of μ and x) will play a crucial role later. Although a similar notion was introduced in <cit.>, the sets of bad projections we use here are far more flexible and also more involved, depending on the decomposition into regular measures provided by Corollary <ref>.

Given θ∈ S^1, we denote the orthogonal projection x↦ x·θ by Π_θ.  Normalized Lebesgue measure on S^1 will be denoted by |·|. We recall the following consequence of the energy version of Marstrand's projection theorem.
 
Let μ∈([0,1)^2) have finite 1-energy. Then, for any R>0,

    |{θ∈ S^1: Π_θμ_2^2 ≥ R  _1(μ) }| ≲ R^-1.



This is just a consequence of Markov's inequality and the identity

    ∫_S^1Π_θμ_2^2 dθ≲_1(μ).

see e.g. <cit.>.



We restate  <cit.> using our notation, for later reference.
 
For any ν∈(^2), k∈ and θ∈ S^1,

    R_k Π_θν_2^2 ≈Π_θ R_k ν_2^2.




Next, we define the various sets of “bad projections”.
 
Given μ∈([0,1)^2),  x∈_𝖽(μ) and non-negative integers j,k, j_0, ℓ, we let

    (μ,x,j, k)    = {θ∈ S^1: Π_θμ(x;j j+k) _2^2 ≥ 2^ T k_1(μ(x;j j+k)) }, 
    _j_0ℓ(μ,x)    = ⋃{(μ,x,j,k) : k ≥τ j,    j_0≤ j ≤ j+k≤ℓ}.


We underline that the definition of _j_0ℓ(μ,x) depends on the parameters T, and τ. Note that, since μ(x;j j+k) has a bounded density by definition, both quantities in the definition of (μ,x,j, k) are finite.

Our next goal is to combine Lemma <ref> with the decomposition given by Corollary <ref>. Starting with a 2^-Tℓ-measure μ∈([0,1)^2) and x∈_𝖽(μ), we define

    '_j_0ℓ(μ,x) = _j_0ℓ(μ_X_j,x)      if x∈ X_j
    ∅    if  x∈_𝖽(μ)∖⋃_i X_i
    ,

where (X_i)_i=1^N are the sets given by Corollary <ref>. Note that _𝖽(μ_X_j)=X_j.

 
There exists a further constant '='(T,,τ)>0 such that, for any 2^-Tℓ-measure μ∈([0,1)^2),

    |'_ℓℓ(μ,x)|  ≲_T,,τ 2^-' ℓ  for all x∈_𝖽(μ).



According to the definitions and Lemma <ref>, for any ν∈([0,1)^2) and x∈_𝖽(ν),

    |_j_0ℓ(ν,x)| ≲∑_j=j_0^∞∑_k=⌊τ j⌋^∞ 2^- T k≲_T,,τ  2^- T τ j_0 .

The point here is that the bound does not depend on ν or x. Hence the claim follows with '  = ^2 Tτ.


Finally, if μ∈([0,1)^2) and x∈_𝖽(μ), we let

    ”_ℓ_0(μ,x) =⋃_ℓ=ℓ_0^∞'_ℓℓ(R_ℓμ,x).

We record the following immediate consequence of Lemma <ref> for later use.
 

    |”_ℓ_0(μ,x)| ≲_T,,τ 2^-' ℓ_0,

for all x∈_𝖽(μ), where '='(T,,τ)>0 is the constant from Lemma <ref>.





 §.§ Radial projections



The following result was recently established by T. Orponen <cit.>. We state it only in the plane. We denote the radial projection with center y by P_y, i.e. P_y(x)=(y-x)/|y-x|∈ S^1 is the (oriented) direction determined by x and y.
 
Let μ,ν∈([0,1)^2) be measures with disjoint supports, such that _s(μ)<∞, _u(ν)<∞ for some u>1, 2-u<s<1. Then there is p=p(s,u)>1 such that P_xν is absolutely continuous with a density in L^p(S^1) for μ almost all x. Moreover,

    ∫P_xν_p^p  dμ(x) <∞.



This is stated in <cit.>, except that Orponen deals with weighted measures μ_y=|x-y|^-1dμ instead of μ (note that the roles of μ and ν are interchanged in <cit.>). Since the weight |x-y|^-1 is bounded away from 0 and ∞ by the assumption that the supports of μ and ν are bounded and disjoint, the claim also holds for μ.


We point out that Proposition <ref> uses the Fourier transform, and is the only point in the proofs of Theorems <ref> and <ref> that does (on the other hand, the proof of Theorem <ref> relies heavily on the strongly Fourier-analytic approach of Mattila-Wolff).

Proposition <ref> has the following key consequence. A similar statement was obtained in <cit.> using a slightly more involved argument. We recall that |·| stands for normalized Lebesgue measure on the circle.

 
Let μ,ν∈([0,1)^2) have disjoint supports and satisfy _s(μ), _u(ν)<∞ for some s∈ (0,2), u>max(1,2-s). Then there exists κ=κ(μ,ν)>0 such that the following holds:

Suppose that Θ⊂ [0,1)^2× S^1 is a Borel set such that

    (μ×ℋ^1)(Θ) ≤κ.

Then

    (μ×ν){ (x,y): P_y(x) ∉Θ_x } > 2/3.



Since _s(μ)<∞ implies that _s'(μ)<∞ for all s'<s, we may assume that s<1. By Proposition <ref>, there is p>1 such that

    ∫P_xν_p^p  dμ(x) =: C <∞.

Denote Θ_x = {θ∈ S^1: (x,θ)∈Θ}
and -Θ_x={ -θ:θ∈Θ_x}. Using Fubini and Hölder, each twice, we estimate

    (μ×ν){(x,y): P_y(x)∈Θ_x}   = ∫ P_xν(-Θ_x) dμ(x)
       ≤∫ℋ^1(Θ_x)^1/p'P_xν_p  dμ(x)
       ≤(∫ℋ^1(Θ_x) dμ(x))^1/p'(∫P_xν_p^p dμ(x))^1/p
       ≤κ^1/p'  C^1/p.

The claim follows by choosing κ so that κ^1/p' C^1/p≤ 1/3.




§ BOX-COUNTING ESTIMATES FOR PINNED DISTANCE SETS



In this section we derive a lower bound on box-counting numbers of pinned distance sets that will be crucial in the proofs of Theorems <ref> ,<ref> and <ref>. Our estimate will be in terms of a multiscale decomposition where, unlike previous works in the literature, we are allowed to choose the sequence of scales (depending on the set or measure for which we are seeking estimates). This additional flexibility will ultimately allow us to improve upon the easy bounds on the dimensions of distance sets.

To begin, we recall some basic facts about entropy. If ν∈(^d) and 𝒜 is a finite partition of ^d (or of a set of full ν-measure), then the entropy of ν with respect to 𝒜 is given by

    H(ν,𝒜) = -∑_A∈𝒜ν(A) log(ν(A)),

with the usual convention 0·log 0=0. It follows from the concavity of the logarithm that one always has

    H(ν,𝒜) ≤log|𝒜|.

Hence, a lower bound for H(ν,_j) provides a lower bound for (A,j) if A is a Borel set of full measure (recall that (A,j) denotes the number of elements in _j that intersect A). We will apply this when ν is supported on a pinned distance set. Although box-counting numbers in principle give bounds only for box dimension, together with standard mass pigeonholing arguments we will be able to get bounds also for Hausdorff and packing dimension.

The following proposition is the key device that will allow us to bound from below the entropy of pinned distance measures (and hence also the box-counting numbers of pinned distance sets). Roughly speaking, we bound the entropy of the projection of a measure μ under the pinned distance map by an average over both scales and space (the latter, weighted by μ) of a quantity involving the L^2 norms of projected local pinned distance measures. We emphasize that this method to bound the dimension of (linear or nonlinear) projections from below goes back in various forms to <cit.>, although the use of projected L^2 norms (rather than projected entropies) was first used in <cit.>.

Before stating the proposition we introduce some definitions. Given L∈, a good partition of (0,L] is an integer sequence 0=N_0<…<N_q=L such that N_j+1-N_j≤ N_j+1. We write Δ_y(x)=|x-y| for the pinned distance map, and θ(x,y)=P_y(x)=(x-y)/|x-y|.


 
Let μ∈([0,1)^d), let y∈^d be at distance ≥ from (μ), and fix a good partition (N_i)_i=0^q of (0,ℓ]. Then

    Tℓ -  H(Δ_yμ,_ℓ) ≤ O_T,(q)  + ∑_i=0^q-1∑_Q∈_N_iμ(Q)  logΠ_θ(x_Q,y)μ(Q;N_i+1) _2^2,

where  x_Q is an arbitrary point in Q.


Write D_i=N_i+1-N_i. Note that our _i correspond to _T i  and our T N_i to m_i in <cit.>. Recall also that μ^Q denotes the magnification of μ_Q to the unit cube. It is shown in <cit.> that

    H(Δ_yμ,_ℓ) ≥ -O_T,(q) +∑_i=0^q-1∑_Q∈_N_iμ(Q) H(Π_θ(y,x_Q)μ^Q ,_D_i).


Applying Lemma <ref> to ν = μ^Q for some Q∈_N_i and k=D_i, we get that

    R_D_iΠ_θ(y,x_Q)μ^Q _2^2 ≈Π_θ(y,x_Q)μ(Q;N_i+1) _2^2.

On the other hand, a simple convexity argument (see <cit.>) yields that, for any ν∈() and k∈,

    H(ν,_k) ≥  Tk - logR_k ν_2^2.

Applying this with k=D_i and ν = Π_θ(y,x_Q)μ^Q, and recalling (<ref>), we deduce that

    H(Π_θ(y,x_Q)μ^Q ,_D_i) ≥   T D_i - logΠ_θ(y,x_Q)μ(Q;N_i+1) _2^2 - O(1).

Using this bound in each term in the right-hand side of (<ref>), and absorbing the sum of the q O(1) terms into O_T,(q), we get the claim.


We remark that the assumption that N_j+1-N_j≤ N_j+1 in the definition of good partition (which will play a crucial role later) arises from the linearization of the distance function, and cannot be substantially weakened. The key advantage of having L^2 norms instead of entropies in this proposition is that the estimate one gets is robust under passing to subsets of moderately large measure:
 
With the assumptions and notation from Proposition <ref>, let us write ℱ(μ) for the right-hand side of (<ref>) (we assume y and the partition (N_i) are fixed). If μ∈([0,1)^2), ν=μ_A where A is Borel and μ(A)>0,  then

    ℱ(ν) ≤ O_T,(q) + 2qlog(Tℓμ(A))  + ∑_i=0^q-1∑_Q∈_N_iν(Q)  logΠ_θ(y,x_Q)μ(Q;N_i+1) _2^2.



We start with the trivial observation that if ρ,ρ'∈(^d) have an L^2 density and ρ'(S)≤ Kρ(S) for all Borel sets S, then the same bound transfers over to the densities for a.e. point, and so ρ'_2^2 ≤ K^2 ρ_2^2.

Let ζ=1/(Tℓ)∈ (0,1). Fix i∈{0,…,q-1}, and note that

    ∑{ν(Q): Q∈_N_i, ν(Q) < ζμ(Q)} < ζ.

Suppose ν(Q) = μ(A∩ Q)/μ(A) ≥ζμ(Q)>0 for a given Q∈_N_i. Then

    ν_Q(S) = μ(A∩ Q∩ S)/μ(A∩ Q)≤μ(Q∩ S)/ζμ(A)μ(Q) = 1/ζμ(A)μ_Q(S)

for any Borel set S⊂ [0,1)^2. This domination is preserved under push-forwards and the action of R_D_i (where as before D_i = N_i+1-N_i), so in light of our initial observation we get

    Π_θ(y,x_Q)ν(Q;N_i+1)  _2^2 ≤1/(ζμ(A))^2Π_θ(y,x_Q)μ(Q;N_i+1) _2^2 ,

always assuming that ν(Q)≥ζμ(Q)>0 and Q∈_N_i. Also, since the measure Π_θ(y,x_Q)μ(Q;N_i+1) is supported on an interval of length √(2), it follows from Cauchy-Schwarz that

    Π_θ(y,x_Q)μ(Q;N_i+1) _2^2 ≥ 2^-1/2.


On the other hand, for any 2^-T D-measure ρ on  one has ρ_2^2 ≤ 2^T D. In light of Lemma <ref>, this implies that

    Π_θ(y,x_Q)ν(Q;N_i+1) _2^2 ≲ 2^T D_i.

Splitting (for each i) the sum ∑_Q∈_N_i in Proposition <ref> into the cubes with ν(Q) ≥ζμ(Q) and ν(Q)< ζμ(Q), and recalling (<ref>), we arrive at the estimate

    ℱ(ν) ≤ O_T,(q) + ζ Tℓ - 2qlog(ζμ(A))  + ∑_i=0^q-1∑_Q∈_N_i
    ν(Q)≥ζμ(Q)ν(Q)   logΠ_θ(y,x_Q)μ(Q;N_i+1) _2^2,

where we merged the sum of the (log of the) implicit constants in (<ref>) into O_T,(q). Recalling that ζ=1/(Tℓ)  and using  (<ref>) we get the desired result.


Our next goal is to get a simpler lower bound in the context of Proposition <ref> when μ is σ-regular (recall Definition <ref>), and ν is the restriction of μ to the set of points which are not bad in the sense of <ref>. Combining the results of <ref> and <ref>, we will later be able to deal with general measures via a reduction to this special case.

We require some additional definitions:
 
We say that 0=N_0<N_1<…<N_q=L is a τ-good partition of (0,L] if

    τ N_j ≤ N_j+1-N_j ≤ N_j+1

for every 0≤ j< q. In other words (N_j) is a good partition and additionally N_j+1≥ (1+τ) N_j.

Given a finite sequence (σ_1,…,σ_L)∈^L, let

    𝒮(σ) = -min_j=0^L σ_1+⋯+σ_j ≥ 0.



For any good partition 𝒫=(N_j)_j=0^q of (0,L] and any σ∈^L, we denote

    (σ,𝒫) = ∑_j=0^q-1𝒮(σ|(N_j,N_j+1]),

where σ|I denotes the restriction of the sequence σ to the interval I.

Finally, given σ∈^L and τ∈ (0,1), we let

    _τ(σ) = min{(σ,𝒫) : 𝒫 is a τ-good partition of  (0,L]}.



Recall that o_T,(1) denotes a function of T and  which tends to 0 as T→∞,→ 0^+.
 
Suppose that ρ∈([0,1)^2) is a (σ_1,…,σ_ℓ)-regular measure. Assume that there are a Borel set A⊂ [0,1)^2, a point y∈^2 and a number β∈ (0,1) satisfying that ρ(A)>0, (y,(ρ))≥, and for all x∈ A∩_𝖽(ρ) there is x∈_ℓ(x) such that

    θ(x,y) ∉_βℓℓ(ρ,x).

Then

    log(Δ_y A,ℓ)/Tℓ≥ 1 - _τ(σ)/ℓ -  .

where

    = 2β + o_T,(1) +  O_T,,τ(log^2ℓ/ℓ) + O_τ(logℓ)log(1/ρ(A))/ℓ.



Let =(N_i)_i=0^q be a τ-good partition of (0,ℓ]. We have to show that

    log(Δ_y A,ℓ)/Tℓ≥ 1 - (σ,𝒫)/ℓ  -  .


Fix i_0 as the smallest value of i such that N_i≥βℓ, and note that N_i_0<  2βℓ+1.

Let us rewrite the inequality from Proposition <ref> applied to ρ and ρ_A in the form

    ℱ(ρ_A) ≤ E + Σ_I + Σ_II,

where

    E    =  O_T,(q) + 2qlog(Tℓρ(A)),
    Σ_I   =  ∑_i=0^i_0-1∑_Q∈_N_i: ρ(A∩ Q)>0ρ_A(Q)  logΠ_θ(y,x_Q)ρ(Q;N_i+1) _2^2,
    Σ_II   =  ∑_i=i_0^q-1∑_Q∈_N_i: ρ(A∩ Q)>0ρ_A(Q)  logΠ_θ(y,x_Q)ρ(Q;N_i+1) _2^2,

where x_Q are arbitrary points in Q. By assumption, we may choose these points so that

    θ(x_Q,y)∉_βℓℓ(ρ,x_Q).

Using that  (1+τ)^q≤ℓ, we bound

    E ≤ O_T,,τ(log^2ℓ)+ O_τ(logℓ) log(1/ρ(A)).

Write D_i=N_i+1-N_i. To estimate Σ_I, we use the trivial bound R_D_i(·)_2^2 ≤ 2^D_i T together with Lemma <ref> and the bounds N_i_0<2βℓ +1, (1+τ)^q ≤ℓ, so that

    Σ_I   ≤∑_i=0^i_0-1∑_Q∈_N_iρ_A(Q) (D_i T + O(1)) 
       ≤ N_i_0 T + O(i_0) 
       ≤ 2β Tℓ  + O_T,τ(logℓ).

Now, to estimate the main term Σ_II, we need to go back to Definition <ref>. By (<ref>), and using that  is a τ-good partition of (0,ℓ], we have θ(x_Q,y)∉(ρ,x_Q,N_i,D_i) for i_0 ≤ i < q. We deduce that

    logΠ_θ(x_Q,y)ρ(Q;N_i+1) _2^2 ≤ T D_i +log_1(ρ(Q;N_i+1)),

for i_0 ≤ i < q. On the other hand,  by the assumption that ρ is (σ_1,…,σ_ℓ)-regular, and since  is a good partition of (0,ℓ], the measure  ρ(Q;N_i+1) is (σ_N_i+1,…,σ_N_i+1)-regular. Hence, using Lemma <ref>, we obtain

    log_1(ρ(Q;N_i+1)) ≤ O(D_i) + O_T(1)  + T 𝒮(σ|(N_i,N_i+1]).

Combining the last two displayed formulas, we deduce that

    logΠ_θ(x_Q,y)ρ(Q;N_i+1) _2^2 ≤ o_T,(1) T D_i+ O_T(1) +  T 𝒮(σ|(N_i,N_i+1]).

Adding up from i=i_0 to q-1 and again using q= O_τ(logℓ), we get

    Σ_II≤ o_T,(1) T ℓ + O_T,τ(logℓ)+ T (σ,).

Combining (<ref>), (<ref>) and (<ref>), we conclude that

    1/Tℓℱ(ρ_A) ≤1/ℓ(σ,) + ,

where  is as in the statement. Recall that ℱ(μ) denotes the right-hand side of (<ref>) in Proposition <ref>. Now Proposition <ref> guarantees that

    1/Tℓ H(Δ_yρ_A,_ℓ) ≥ 1 -  1/ℓ(σ,) - .

Since H(μ,𝒜) ≤log|𝒜| for any finite Borel partition 𝒜 of a set of full μ-measure, this finishes the proof.



Note that in this proposition, the sequence σ depends on the measure ρ and the bound is in terms of M_τ(σ) (we will be able to make the error term arbitrarily small). Thus we are led to the combinatorial problem of minimizing (σ,(N_i)) over all τ-good partitions for a given σ∈ [-1,1]^ℓ. This problem will be tackled in the next section: see Proposition <ref>, and also Proposition <ref> for the case in which we are allowed to restrict σ to (0,L] for some large L.




§ FINDING GOOD SCALE DECOMPOSITIONS: COMBINATORIAL ESTIMATES





 §.§ An optimization problem for Lipschitz functions


We begin by defining suitable analogs of the concepts from Definition <ref> for Lipschitz functions, instead of [-1,1]-sequences.


A sequence (a_n)_n=0^∞ is a partition of
the interval [0,a] if a=a_0>a_1>…>0 and a_n→ 0;
it is a good partition if
we also have a_k-1 / a_k≤ 2 for every k≥ 1.

A sequence (a_n)_n=0^∞ is a τ-good partition for a given 0< τ <1
if it is a good partition and we also have a_k-1 / a_k≥ 1+τ for every k≥ 1.

  Let f:[0,a]→ be continuous and (a_n) be a  partition of [0,a]. By the
  total drop of f according to (a_n) we mean

    (f,(a_n))=∑_n=1^∞ f(a_n)-min_[a_n,a_n-1] f,

and we also introduce the notation

    (f)=inf{ (f,(a_n)) : (a_n)  is a good partition of  [0,a] },


    _τ(f)=inf{ (f,(a_n)) : (a_n)
     is a τ-good partition of  [0,a] }.


We call the interval [a_n,a_n-1] increasing
if min_[a_n,a_n-1] f=f(a_n) and decreasing if
min_[a_n,a_n-1] f=f(a_n-1). (Note that f needs not be increasing or decreasing on [a_n,a_n-1].)



In this section we investigate the following question: given a 1-Lipschitz function f:[0,a]→ satisfying certain bounds,
how large can (f) and _τ(f) be?

First we study (f).
Later we show (see Corollary <ref>)
that for small τ the quantities (f) and
_τ(f) are close.
Finally, from the bounds on T_τ(f) we deduce corresponding bounds  on _τ(σ): see for example Proposition <ref>. Hence this problem is closely related to that of minimizing the dimension loss when estimating the dimension of the pinned distance set via
 Proposition <ref>. Dealing first with Lipschitz functions rather than [-1,1]-sequences allows us to avoid certain technicalities and make the arguments more transparent.

The basic result is the following.


  Let a>0,
-1≤ D < C ≤ 1

be given parameters such that C≥ 2D.
  Let f:[0,a]→ be a 1-Lipschitz function such that
  Dx≤ f(x)≤ Cx for every x∈[0,a].
Then

    (f)≤(a-f(a))(C-2D)/1+2C-3D≤  a·(1-D)(C-2D)/1+2C-3D.





Since f(a)≥ Da and a>0,
the second inequality of
(<ref>) is clear, so it enough to
prove the first inequality.

Let

    h=C-2D/1+C-D  and  ρ=C-2D/1+2C-3D.

Note that

    h=ρ/1-ρ  and  ρ=h/h+1

and h,ρ≥ 0 since we assumed C≥ 2D and C≥ D, so 2C≥ 3D.

We will construct a good partition (a_n) with the following two extra properties:

(*) every interval [a_n,a_n-1] (n=1,2,…) is either increasing or decreasing (recall Definition <ref>), and

(**) if [a_k,a_k-1],…,[a_l+1,a_l] (k ≥ l+1 ≥ 1)
is a maximal block of consecutive decreasing intervals, then

    f(a_k)-f(a_l)/a_l-a_k≤ h=C-2D/1+C-D.


First we show that this is enough to prove
our claim.
Let a=a'_0>a'_1>… be the endpoints of the union of each maximal block of consecutive intervals of the same type (increasing or decreasing).
It easily follows from the definitions and telescoping that
(f,(a_n))=(f,(a'_k)).
Hence to obtain (<ref>) it is enough to
prove

    (f,(a'_k)) ≤ρ·(a-f(a)).


We claim that

    f(a'_k)-min_[a'_k,a'_k-1] f ≤ρ((a'_k-1-f(a'_k-1)) - (a'_k-f(a'_k)))      (k=1,2,…).


Indeed, by construction, the interval [a'_k,a'_k-1] is either increasing or decreasing.
If it is increasing then

    f(a'_k)-min_[a'_k,a'_k-1] f = 0 ≤ρ((a'_k-1-f(a'_k-1)) - (a'_k-f(a'_k)))

since f is 1-Lipschitz and a'_k<a'_k-1.


If  [a'_k+1,a'_k] is decreasing then, using first (**) and the fact that ρ<1, and then (<ref>), we get

    f(a'_k)-min_[a'_k,a'_k-1] f    =
    f(a'_k)-f(a'_k-1) 
       ≤ρ(f(a'_k)-f(a'_k-1)) + (1-ρ)h(a'_k-1-a'_k)
    
       = ρ(f(a'_k)-f(a'_k-1)) + ρ (a'_k-1-a'_k),

which completes the proof of (<ref>).

By adding up (<ref>) for k=1,2,… and
using that a'_0=a, a'_k→ 0 and f(a'_k)→ 0
we get (<ref>), which implies (<ref>).

Therefore it is enough to construct a good 
partition (a_n) with properties (*) and (**).
Let a_0=a and suppose that a_0>…>a_n>0 are already constructed
with properties (*) and (**) (up to n).

We distinguish three cases.

Case 1. min_[a_n/2,a_n] f < f(a_n).

In this case let a_n+1∈ [a_n/2,a_n] be the smallest
number such that
f(a_n+1)=min_[a_n/2,a_n]f. Then [a_n+1,a_n]
is an increasing interval and so (*) and (**) still hold and we can continue the procedure.

Case 2. min_[a_n/2,a_n] f = f(a_n) and
f(a_n/2)-f(a_n)≤ h· (a_n - a_n/2).

In this case let a_n+1=a_n/2, and again (*), (**) hold for the extended sequence and we can continue the procedure.

Case 3. min_[a_n/2,a_n] f = f(a_n) and
f(a_n/2)-f(a_n)> h· (a_n - a_n/2).

First we claim that h≥ -D. Indeed, since -1≤ D≤ C we have

    0≤ (C-D)(D+1)=-D+CD-D^2+C,

which  implies that

    -D(1+C-D) ≤ C-2D ,

and this implies h≥ -D.

Since h≥ -D and f(x)≥ Dx we have
f(a_n)≥ Da_n≥ -ha_n and so

    f(0)-f(a_n)=-f(a_n)≤ h a_n = h (a_n-0).


This and the assumption
f(a_n/2)-f(a_n)> h· (a_n - a_n/2)
implies that there exists
a largest b∈[0,a_n/2) be such that

    f(b)-f(a_n)=h(a_n-b).


Now our goal is to find a sequence b=b_0<b_1<…<b_M=a_n with M≥ 2
such that

    min_[b_i-1,b_i]f=f(b_i), b_i/b_i-1≤ 2 (i=1,…, M),
       b_i/b_i-2≥ 2 (i=2,…,M).


The sequence (b_i) is constructed by induction.
Let b_0=b.
Suppose that m≥ 0, b=b_0<…<b_m< a_n
are already constructed and (<ref>) holds for M=m.
If b_m≥ a_n/2 then we can take b_m+1=a_n and M=m+1.
Then the construction is completed and (<ref>) holds.

Now consider the case b_m< a_n/2.
Let b_m+1∈[b_m,2b_m] be maximal
such that f(b_m+1)=min_[b_m,2b_m]f.
Our goal is to show that b_m+1>b_m.
For this it is enough to show that f(2b_m)≤ f(b_m).

Using that b is the largest number in [0,a_n/2]
for which (<ref>) holds,
b_m≥ b and  f(a_n/2)-f(a_n)> h· (a_n - a_n/2),
we get

    f(b_m)-f(a_n)≥ h(a_n-b_m).


Hence to get
f(2b_m)≤ f(b_m) it is enough to show that

    f(2b_m)-f(a_n)≤ h(a_n-b_m).

Using (<ref>) and Dx≤ f(x)≤ Cx we get

    h(a_n-b_m)≤ f(b_m)-f(a_n)≤ Cb_m-Da_n,

which implies that

    (D+h)a_n≤ (C+h)b_m.

Direct calculation shows that D+h=(C-D)(1-h) and C+h=(C-D)(2-h).
Thus the last inequality
 and D<C imply

that

    (1-h)a_n≤ (2-h)b_m.

Hence, using also that f is 1-Lipschitz
and b_m<a_n/2, we obtain

    h(a_n-b_m)≥ a_n - 2b_m ≥ f(2b_m)-f(a_n).

This completes the proof of (<ref>) and so also the proof
of b_m+1>b_m.
It is easy to see that (<ref>) holds for M=m+1.
Note also that the property b_i/b_i-2≥ 2 implies that
the construction of the sequence (b_i) is completed after
finitely many steps.

Now, to finish Case 3 we take a_n+j=b_M-j for j=1,…,M.
Then (*) and (**) hold (up to n+m) and so the procedure can be continued.

This way we obtain a sequence
a=a_0>a_1>…>0 that forms
a good partition with (*) and (**), provided a_n→ 0.
Therefore it remains to prove that a_n→ 0.

Since a_n+1=a_n/2 when Case 2 is applied and
a_n+M=b_0=b≤ a_n/2 in Case 3, we are done if Case 2 or Case 3
is applied infinitely many times.
It is easy
to see that if both a_n+1 and a_n+2 were
obtained from Case 1, then we have a_n/a_n+2≥ 2.
Thus a_n→ 0, which completes the proof.




 §.§ Small drop on initial segments


The results in this subsection are required in the proof of Theorem <ref>. We  aim to minimize (f|[0,u])/u, where u>0 is a new parameter that we are allowed to choose, subject to not being too small. The analysis will be strongly based on the study of hard points which we now define:
 
If f:[0,a]→ is a function, we say that p∈[0,a] is a hard point of f if min_[p/2,p] f=f(p).


We will say that a function f defined on an interval I is piecewise linear if I can be decomposed
into finitely many intervals such that f is linear on each of them.

Let f:[0,a]→ be a 1-Lipschitz function,
which is piecewise linear on every closed subinterval of (0,a]. Then:

(i) The set of hard points of f can be written as a
(possibly empty) finite or infinite union of closed
(possibly degenerate) intervals
H = ∪_j [u_j,v_j]
such that
v_1≥ u_1>v_2≥ u_2>… and
every closed subinterval of (0,a]
intersects only finitely many [u_j,v_j].

(ii) We have

    (f)=∑_j f(u_j)-f(v_j),

where the empty sum is meant to be zero.



The first statement is easy,
using that f is piecewise linear.

First we prove ≥ in (<ref>).
Let
 (a_n) be a good partition of [0,a] and let
a=a'_0>a'_1>… be an ordered enumeration
of the set {a_n}∪{u_j}∪{v_j}. It is easy to check that (a'_n)
is also a good partition of [0,a], and that by inserting a hard point of
f into a good partition (a_n), the value of (f,(a_n)) is
not changed. Thus (f,(a'_n))=(f,(a_n)).
Now every [u_j,v_j] is of the form
[u_j,v_j]=∪_n=n_j^m_j [a'_n,a'_n-1].
Since f must be nonincreasing on
any interval [u_j,v_j] we obtain

    f(u_j)-f(v_j)=
    ∑_n=n_j^m_j f(a'_n)-min_[a'_n,a'_n-1] f

for every j.
Adding up, and using that
f(a'_n)-min_[a'_n,a'_n-1] f≥ 0 and
(f,(a'_n))=(f,(a_n)) we get the claim.

To prove the other inequality we
construct by induction a good partition of [0,a]
such that (f,(a_n))≤∑_j f(u_j)-f(v_j).
Let a_0=a.
Suppose that a_0,…,a_n are already defined.

Case 1. If a_n∈ (u_j,v_j] for some j then choose k≥ 1 and
a_n>a_n+1>…>a_n+k=u_j so that
a_n+i/a_n+i-1≤ 2 for i=1,…,k.

Case 2. Otherwise let a_n+1∈[a_n/2,a_n] be the
smallest number for which
f(a_n+1)=min_[a_n/2,a_n]f.
We claim that a_n+1<a_n.
If a_n∉H then this is clear from the definition.
Since the only points of H that are not handled
in the previous case are the left endpoints of the
intervals [u_j,v_j] we can suppose that a_n=u_j
for some j.
By the piecewise linearity of f, there exists  w∈ (u_j/2, u_j)
such that f is linear on [w,u_j] and
w>v_j+1.
Since u_j is a hard point, f cannot be increasing
on [w,u_j]. If f is constant on [w,u_j]
then a_n+1≤ w<u_j=a_n, so we are done.
So we can suppose that f is decreasing on [w,u_j].
Since w>v_j+1, every  x∈ [w,u_j) is
not hard, so there exists an x'∈[x/2,x) such that
f(x')<f(x).
Since f is decreasing on [w,u_j], x'<w.
By the continuity of f, this implies that there exists
x_0∈[u_j/2,w] such that f(x_0)≤ f(u_j). Thus indeed a_n+1<u_j=a_n.

Note that if Case 2 was applied to obtain both a_n+1 and
a_n+2 then a_n/a_n+2≥ 2.
This implies that a_n→ 0, so (a_n) is a good
partition of [0,a]. It remains to show that
(f,(a_n))≤∑_j f(u_j)-f(v_j).

If a_n was obtained in Case 1 then
[a_n,a_n-1] is a subinterval of some [u_j,v_j] and
f(a_n)-min_[a_n,a_n-1] f=f(a_n)-f(a_n-1).
If a_n was obtained in Case 2 then
f(a_n)-min_[a_n,a_n-1] f=0.
Note also that f is nonincreasing on each [u_j,v_j]
since all points of [u_j,v_j] are hard points of f.
These show that indeed (f,(a_n))≤∑_j f(u_j)-f(v_j),
which completes the proof.


The next proposition (or rather, the discrete corollary given in Proposition <ref> below) will be crucial to get estimates on the packing dimension of the pinned distance sets.


  Let a>0 and  0≤ D < 1/2 be given parameters.
  Let f:[0,a]→ be a 1-Lipschitz function,
  which is piecewise linear on every closed subinterval of (0,a],
  and suppose that
 f(0)=0 and
  Dx≤ f(x) for every x∈[0,a]. Let

    Φ(D)=2-D-√(3-3D^2)/4.


Then for every δ∈(0,1/2)
there exists  u∈[3aΦ(D)2^-1/δ,a]
such that
   
    (f|[0,u]) < u· (Φ(D) +
        δ(2-4logδ)).





Let H[0,a] be the set of hard points of f.
If H=∅ then by Lemma <ref>,
(f)=0, so u=a is clearly a good choice in
this case. So suppose that H is nonempty.

First we briefly explain the idea of the proof in this
nontrivial case. For simplicity, suppose that a=1 and
D=0, which is the most interesting case anyway.
Assume that the maximum of f(x)/x on  H∩ (0,1] exists and is attained at u, and let B be this
maximum. Since u is a hard point, f(x)≥ f(u)=Bu
on [u/2,u], and a calculation using that f is 1-Lipschitz shows that
that

    f(x)> Bx   if   u'<x<u,
    
    
      where u'=1/2-B/1-Bu.

Let F(x)=min(f(x),2B x). Then it is not hard to show
(see below for details) that every
p∈ H∩ [0,u] is also a hard point of F
and that F=f on H∩ [0,u].
By Lemma <ref> this implies that
(f|[0,u])=(F|[0,u]), so we can study
F|[0,u] instead of f|[0,u].
Let v be the largest number in [0,u) such that
F(v)=Bv. It follows from (<ref>) that also
F(x)> Bx if u'<x<u,


so we must have v≤ u', and hence

    v-F(v)=v(1-B)≤ u(1/2-B)

and F(x)>Bx on (v,u). Since F(x)≤ 2Bx,
for any hard point y of F we must have
F(y)≤ By, and this implies that F has no
hard point in (v,u).
By Lemma <ref> this implies that
(F|[0,u])=(F|[0,v]).
Again using that F(x)≤ 2Bx, we can apply Proposition <ref>
on [0,v] to obtain

    (f|[0,u])=(F|[0,u])=(F|[0,v])≤(v-F(v))(2B-0)/1+2· 2B - 3· 0≤u(1/2-B)2B/1+4B.

Calculus shows that
(1/2-B)2B/1+4B≤2-√(3)/4=Φ(0) for B∈ [0,1],
so we obtain (f|[0,u])≤ uΦ(0).

Unfortunately, f(x)/x may not have
a maximum on H∩ (0,1] and, even if it does, we might get an u which is too small.
To avoid these problems we replace f(x)/x
by f(x)/x +δlog x. Then we can show that u exists, is not too small, and it still satisfies the claim of the proposition.

We now continue with the actual proof. Note that H is a closed set, and let h=max H.
By Lemma <ref>,
(f)=(f|[0,h]).


If h<3aΦ(D) then, applying Proposition <ref> on [0,h] with C=1,
we get

    (f)=(f|[0,h])≤(h-f(h))(1-2D)/3-3D≤
    h/3 <aΦ(D),

so u=a is a good choice in this case.

Therefore in the rest of the proof we can suppose that h≥ 3aΦ(D).
Let

    ϕ(x)=f(x)/x+δlog x.

(Recall that in this paper log denotes log_2.)
Since f is nonnegative and 1-Lipschitz, 0≤ f(x)/x≤ 1 on (0,a], so
  for any x∈(0,2^-1/δh) we have
  
    ϕ(x)=f(x)/x+δlog x < 1 +δlog(2^-1/δh)
    ≤δlog h ≤f(h)/h+δlog h = ϕ(h).


Now we claim that

    (∃ u∈ H∩ [2^-1/δh, h])  (∀ x∈ H∩ [δ u, u])ϕ(x)≤ϕ(u).



To prove this we define a sequence u_0>u_1>…∈ H inductively. Let u_0=h. Suppose that u_n∈ H is already defined.
Let v∈ H∩[δ u_n, u_n] be the largest number such that
ϕ(v)=max_H∩ [δ u_n, u_n]ϕ.
If v=u_n then let N=n and the procedure is terminated.

Otherwise letting u_n+1=v we have u_n+1<u_n,
so the procedure can be continued.
Note that it follows from the construction that
ϕ(h)=ϕ(u_0)≤…≤ϕ(u_n) and
u_n+2<δ u_n (n=0,1,…).
Thus (<ref>) implies that the procedure must be terminated
in finitely many steps and (<ref>) holds for u=u_N.

Let u be chosen according to (<ref>).
Then, using that h≥ 3aΦ(D), we have
u≥ 2^-1/δh≥ 2^-1/δ· 3aΦ(D),
so the requirement u∈[3aΦ(D)2^-1/δ,a]
is satisfied.
Thus it remains to prove (<ref>).

Let

    B=f(u)/u-δlogδ.

Since u is chosen according to (<ref>), we have

    (∀ x∈ H∩[δ u,u])   
     f(x)≤ x(f(u)/u+δlogu/x)
     ≤ x(f(u)/u-δlogδ) = Bx.

Let F(x)=min(f(x),2Bx) (x∈[0,u]).

Now we claim that every p∈ H∩[δ u,u] is also a hard point of F.
Suppose, on the contrary, that p∈ H∩[δ u,u] is not a hard point of F.
Then there exists a q∈[p/2,p] such that F(q)<F(p).
By (<ref>) we have f(p)≤ Bp≤ 2Bp, so by definition F(p)=f(p),
and consequently we have

    F(q)<F(p)=f(p)≤ Bp≤ 2Bq,

which implies that f(q)=F(q). Thus f(q)<f(p), so p cannot be a hard point of f, which is
a contradiction.

Note that, by Lemma <ref> and
since F(p)=f(p) for any hard point of F,
the above claim
and the trivial estimate (f|[0,δ u])≤δ u
imply

    (f|[0,v])≤(F|[0,v])+δ u     for any  v∈[0,u].


First we consider the case when f(u)/u<-δlogδ.

Then B<-2δlogδ, and so

    0≤ F(x)≤ 2Bx < (-4 δlogδ) x   on [0,u].

If -4δlogδ >1 then,
since Φ(D)≥ 0 for D≤ 1/2,
the righthand-side of (<ref>) is
larger than u.
Since clearly (g)≤ u for
any 1-Lipschitz function g:[0,u]→
we are done if -4δlogδ >1. So we may suppose that -4δlogδ≤ 1.











By Proposition <ref> applied to F, with a=u, C=-4δlogδ and D=0,
 we obtain


    (F)≤
    u·-4 δlogδ/1-8 δlogδ
    < -4 uδlogδ.

By (<ref>) (applied to v=u) this implies that

    (f|[0,u])≤ -4 uδlogδ +δ u.


Since D≤ 1/2, we have Φ(D)≥ 0, so
(<ref>)
implies (<ref>), which completes
the proof in the case when f(u)/u<-δlogδ.

So in the rest of the proof we may assume that

    f(u)/u≥ -δlogδ.


Since δ<1/2 this also implies that f(u)/u>δ.
Putting this together with the fact that u was chosen according to (<ref>), and with the inequality log y≤ y-1, we get that
if x∈ H∩[δ u, u), then

    f(x)≤ xf(u)/u+xδlogu/x<
    xf(u)/u+xf(u)/u(u/x-1)
    = f(u).

Since u is a hard point,  f(x)≥ f(u)
on [u/2,u], and so (<ref>) implies
that H∩[u/2,u)=∅.

Again because u is a hard point, f(u/2)≥ f(u). Using this, δ<1/2
and the fact that f is 1-Lipschitz, we get

    B=f(u)/u-δlogδ <
    f(u/2)/u+1/2≤ 1.

Using again that f is 1-Lipschitz and f(u/2)≥ f(u),
we get

    f(x)≥
    f(u/2)-(u/2-x)≥
    f(u)-(u/2-x)    (x∈ [0,u/2]).

Thus

    f(x)≥ f(u)-(u/2-x)>Bx
      if  u/2-f(u)/1-B < x ≤u/2.

Let v_0= u/2-f(u)/1-B.
Note that f(x)>Bx also holds on the closed interval [v_0,u/2] unless
f(v_0)=Bv_0.
The definition B=f(u)/u-δlogδ
and the assumption (<ref>) imply that
B≤ 2f(u)/u, hence v_0≤ u/2.
Let v=max{x∈[0,u/2] : f(x)=Bx}
(the maximum over a nonempty compact set).
By (<ref>) we have v≤ v_0
and f(x)>Bx on (v,u/2].
By (<ref>),
this implies that
H ∩ [δ u,u]∩ (v, u/2)=∅.
Since above we obtained H∩[u/2,u)=∅
we get
H∩(v,u)[0,δ u].
Hence, using Lemma <ref>
and the trivial estimate T(f|[0, u))≤ u, we get

    (f|[0,u]) ≤(f|[0,v]) +δ u.


Since v≤ v_0=u/2-f(u)/1-B and f(v)=Bv,

    2(v-f(v))=2(1-B)v≤ u-2f(u) =
    u(1-2f(u)/u)=
    u(1-2B-2δlogδ).

Let C=min(2B,1). We have just seen that

    2(v-f(v)) ≤ u(1-C-2δlogδ).

Note also that D≤ f(u)/u=B+δlogδ<B, and so D≤ C/2 since we assumed that D≤ 1/2. Then Dx≤ F(x)≤ Cx on
[0,v] [0,u], so we can apply Proposition <ref> to get

    (F|[0,v])≤(v-f(v))(C-2D)/1+2C-3D≤u(1-C-2δlogδ)(C/2-D)/1+2C-3D.

Note that C/2-D/1+2C-3D< 1. Using calculus, we get that
(1-C)(C/2-D)/1+2C-3D≤Φ(D) for C∈ [2D,1].
Therefore

    (F|[0,v])< u(Φ(D)-2δlogδ).


Combining the above inequality with (<ref>) and
(<ref>),
we get (<ref>).





 §.§ Stability results



The results of this subsection are only needed for the proof of Theorem <ref>. Moreover, to get the bound (Δ(A))≥ 37/54 whenever (A)>1, one only needs to consider the case D=0 below. While there is no conceptual difference between the cases D=0 and D>0, the calculations are easier in the former case, so the reader may want to assume that D=0 in a first reading.

In the C=1 special case of Proposition <ref>, we get that if
D∈ [-1,1/2] and f:[0,1]→ is a  1-Lipschitz function such that
 f(0)=0 and
f(x)≥ Dx on [0,1], then (f)≤ (1-2D)/3.
As we will see in Section <ref>,
and is not hard to check, this estimate is sharp: if

    f(x) =  {[              x             if x∈ [0,(D+1)/2];          1+D-x             if x∈ [(D+1)/2,1] ].,

then (f)=(1-2D)/3. In this section we prove a quantitative stability result
(Proposition <ref>)
for D∈[0,1/3], stating that if (f) is close to (1-2D)/3 then f(x) must be close to the
above function when x is not too far from 0 or
from 1. 

The general plan to get this result is the following.
Let b=min_[1/2,1] f and choose a∈[1/2,1]
such that f(a)=b. It is easy to see that (f)=(f|[0,a]),
so it is enough to study f|[0,a] instead of f.
We need to get an
upper estimate on T(f) when f is not close enough to
the function defined in the previous paragraph.
This upper estimate will be obtained by
finding a point p∈ [0,a] such that
in the good partition in the definition of T(f),
the points a_n in [p,a]
can be chosen such that
min_[a_n,a_n-1]f = f(a_n-1), and so
for these indices the sum of the terms
f(a_n)-min_[a_n,a_n-1]f is
f(p)-f(a) or, in other words, the smallest possible.
Combining this with a near optimal good partition for f|[0,p]
guaranteed by Proposition <ref>, we get a near optimal
lower bound for T(f) for all f with such a special point
p and value f(p). These points p will be called
simple points, and after proving the above described
near optimal upper estimate, most of the proof will be about
hunting a simple point such that the estimate we obtain
for (f) is the upper estimate we claim.



First we collect some assumptions and define precisely
the above mentioned notion of simple points.

  Suppose that
 
    a∈ (0,1], b∈, D∈[0,1/2),    f:[0,a]→ is 1-Lipschitz, 
    
       f(0)=0,    f(x)≥ Dx  (x∈ [0,a])  and min_[a/2,a] f=f(a)=b.

  A point p∈[0,a] is called simple if there exists a finite
  sequence p=p_0<p_1<…<p_k=a such that
  
    p_i/p_i-1≤ 2    and    f(p_i)=min_[p_i-1,p_i] f      (i=1,…,k).




  If (<ref>) holds and p∈[0,a] is a simple point then
  
    (f)≤ p+ (1- ) f(p) -b,
       where  = 1-2D/3(1-D).




  Applying Proposition <ref> to f|[0,p] with C=1 we
  get (f|[0,p])≤ (p-f(p)).
  Hence for any >0 there exists a good partition (a_n) of [0,p]
  such that
  
    (f|[0,p],(a_n))≤ (p-f(p)) + .

  Since p is simple there exists a finite sequence
  p=p_0<p_1<…<p_k=a such that (<ref>) holds.

  For n≤ k let a'_n=p_k-n and for n>k let a'_n=a_n-k.
  Then
( a'_n)

    is a good partition of [0,a] and
  
    (f,( a'_n))
           =   (f|[0,p],( a_n))
    
        +∑_i=1^k f(p_i-1)-f(p_i) 
       ≤    (p-f(p)) +  + f(p) - f(a)
        =  p+ (1- ) f(p)-b +,

  which completes the proof.



  Suppose that (<ref>) holds and let p∈ [0,a].
  If

    for every  z∈[p,a/2)
     there exists  y ∈ (z,2z]
     such that  f(y)≤ f(z)

then p is simple.



  Let p_0=p. Suppose that n≥ 0 and
   p_0<…<p_n are defined such that
  (<ref>) holds for k=n.
  If p_n≥ a/2 then let p_n+1=a and we are done.
  Otherwise, let p_n+1∈[p_n,2p_n] be the largest number such that
  f(p_n+1)=min_[p_n,p_n+1] f.
  By (<ref>) we also have p_n+1>p_n.
  It remains to check that the procedure terminates, which follows
  from the simple observation that p_n+2≥min(2 p_n,a) by definition.



  Suppose that (<ref>) holds.
  If p∈[a/2,a], or if p∈[0,a/2] and f(p)≥ -2p+a+b,
  then p is a simple point.



  The case p∈[a/2,a] is clear, so suppose that
  p∈[0,a/2] and f(p)≥ -2p+a+b.
  Then the 1-Lipschitz property of f implies that for any x∈[p,a]
  we also have f(x)≥ -2x+a+b.
  Since f is 1-Lipschitz and f(a)=b we have f(y)≤ -y+a+b
  for any y∈ [0,a].
  Thus f(x)≥ -2x+a+b≥ f(2x) for any x∈ [p,a/2],
  so Lemma <ref> completes the proof.



  Condition (<ref>) implies that 1-a+2b-2D≥ 0.



Note that
b=f(a)≥ Da, so

    1-a+2b-2D ≥ 1 -a + 2aD - 2D = (1-a)(1-2D) ≥ 0.





  If (<ref>) holds  and
  (f)> 1-2D/3- for some
  ∈ (0,a/3)
  then
 
    f(x) > x - 3(1-D)      on  [0,t_0],
      where  t_0=a+b/3 +(1-D).




 First note that <a/3 implies that t_0<a.
  Since f(0)<-2· 0+a+b and f(a)≥ -2· a + a +b there exists
  a t∈(0,a] such that f(t)=-2t+a+b.
 By Lemma <ref>, t is a simple point,
  so writing = 1-2D/3(1-D) and using Lemma <ref>,
   we get

    (f)    ≤ t + (1-) f(t) - b 
       =  t + (1-) (-2t+a+b) - b 
       = -t/1-D+2-D/3(1-D)(a+b)-b.

Combining this with the assumption
  (f)> 1-2D/3 - and multiplying
  through by 3(1-D),  we get

    3t < (2-D)(a+b)-3(1-D)b-(1-2D)(1-D)+3(1-D),

which can be rewritten as

    3t < a+b+ (1-D)(3 - (1-a+2b-2D)).

By Lemma <ref>, this implies
t < a+b/3 +δ(1-D)=t_0.
Using this and the 1-Lipschitz property of f, we obtain

    f(t_0) ≥
    f(t)-(t_0-t) >f(t)-2(t_0-t) =a+b-2t_0=t_0-3(1-D).

Using again that f is 1-Lipschitz, this gives the claim.



  Suppose that (<ref>) holds,
  0≤ p≤a+b-v/2 < u ≤ a, f(u)=v


 and f(x)≥ v on [p,a+b-v/2].
If v≥ u/2 or f(p)=-2p+u+v,
 then p is simple.



It is useful to note that by the 1-Lipschitz property
of f, the assumptions u≤ a, f(u)=v and f(a)=b imply that
u+v≤ a+b,
 and so u/2≤a+b-v/2.

By Lemma <ref> it is enough to check
(<ref>). So let z∈[p,a/2).
We distinguish three cases.

First suppose that z≥a+b-v/2.
Then, using that f(a+b-v/2)≥ v,
f is 1-Lipschitz, 2z<a and f(a)=b, we get

    f(z)≥ v-(z-a+b-v/2)
    ≥  v-2(z-a+b-v/2)= -2z+a+b≥ f(2z).

Therefore (<ref>) holds in this case.

Now suppose that z∈[u/2, a+b-v/2].
Since we consider only z∈[p,a/2) we also have
z∈ [p, a+b-v/2].
Then f(z)≥ v,

u∈(z,2z] and f(u)=v≤ f(z),
so  (<ref>) holds in this case as well.

Finally, suppose that z∈[p,u/2).
  Then v ≤ f(z)≤  z < u/2, hence we cannot
  have v ≥ u/2, so we must have f(p)=-2p+u+v.
  Using that f is 1-Lipschitz and z≥ p,
  this implies f(z)≥ -2z+u+v.
Since f is 1-Lipschitz and f(u)=v we have
f(x)≤ u+v-x on [0,u].
Thus f(2z)≤ u+v-2z≤ f(z), which completes the proof.



  If (<ref>) holds  and
  (f)> 1-2D/3- for some
  ∈ (0,a/3)

then
  
    f(x)> a+b/3-2(1-D)    on  [t_0,2t_0-6δ(1-D)],
        where 
      t_0=a+b/3 +δ(1-D).




  Let v=a+b/3-2(1-D).
  If v<0 then the claim is clear, so we can suppose that v≥ 0.
  By Lemma <ref>, f(t_0)>v. 
  Thus if the claim is false then there exists a 
  u∈ (t_0,2t_0-6δ(1-D)] such that f(u)=v.

By (<ref>),
we have b≤a/2, which implies

    2t_0-6(1-D)=2(a+b)/3-4(1-D)<a.

Since f(0)≤ v<f(t_0) we also have a largest p∈ [0,t_0) such
  that f(p)=v.
  Then f(x)≥ v on [p,t_0].
  Since a+b-v/2=t_0 and u/2≤ t_0-3(1-D)=v, all the
  assumptions of Lemma <ref> hold, so we get that
  p is simple.

  Then by Lemma <ref> we have
  (f)≤ p + (1-) v - b, where = 1-2D/3(1-D).
  Since p<t_0=v+3δ(1-D), this implies that (f)≤ v+(1-2D)-b.
  Combining this with the assumption (f)> 1-2D/3- we get
  
    v> b+1-2D/3-2(1-D).

  Note that Lemma <ref> implies that b+1-2D/3≥a+b/3,
  so we obtain v> a+b/3-2(1-D),
  which is a contradiction.


From the last lemma and the Lipschitz property of f one can easily derive a good lower estimate also on
[2t_0-6 (1-D),a]. However, the next lemma will lead to an even better (and, as we will see later, sharp) estimate on the right part of [0,a].

  Suppose that (<ref>) holds,
 
    (f) > 1-2D/3-,∈ (0,a/3),
      u ∈ (a/2, a],
      u ≥ 2v + 6(1-D), and 
      f(u)=v.

  Then
  
    u+v> 1+D -31+D/1-2D.




 Since f(0)<-2· 0+u+v and f(a)≥ -2· a + u+v there exists
 a p∈(0,a] such that f(p)=-2p+u+v.
First we prove that p is a simple point.
To get this, by Lemma <ref>, it is enough to check that
p≤a+b-v/2<u and  f(x) ≥ v on [p,a+b-v/2].

Since u∈(a/2,a], v=f(u) and b=min_[a/2,a] f,
we have b≤ v, so a+b-v/2≤ a/2<u.

Note (as in Lemma <ref>) that u+v≤ a+b.
By Lemma <ref>, we have f(t_0)>t_0-3(1-D), where t_0=a+b/3 +δ(1-D).
Then

    2t_0+f(t_0)>3t_0-3(1-D)=a+b≥ u+v=2p+f(p).

  Since f is 1-Lipschitz this implies that p< t_0.
  Using this, u+v≤ a+b and finally
  the assumption u≥ 2v+6(1-D), we get

    p< t_0    = a+b/3+(1-D)
       =a+b/2-a+b/6+(1-D)
       ≤a+b/2-u+v/6+(1-D)≤a+b-v/2.


  On [0,t_0] we have f(x)-x> -3(1-D) by Lemma <ref>,
  on [p,a] we have 2x+f(x)≥ 2p + f(p) = u+v
  by the 1-Lipschitz property of f.
   Taking the linear combination of these inequalities with weights 2/3
  and 1/3, we get
  
    f(x)> u+v/3 - 2(1-D)   on  [p,t_0].

  By the assumption u ≥ 2v + 6(1-D), this gives f(x)≥ v
  on [p,t_0].

  Using that f is 1-Lipschitz and then (<ref>),
  we get that on [t_0,a] we have 2x+f(x)≥ 2t_0 +f(t_0)>a+b,
  which implies that f(x)≥ v also on [t_0,a+b-v/2].

  Therefore, by Lemma <ref>, p is indeed a simple point. Now Lemma <ref> gives

    (f)    ≤ p + (1-)f(p)-b
        = p + (1-)(-2p+u+v)-b
        =(3 - 2) p +(1-)(u+v)-b.

Recalling that =1-2D/3(1-D),
it is easy to check that D<1 implies that 3-2 <0.
 The 1-Lipschitz property of f and f(0)=0 imply that
 0≤ p-f(p)=3p-(u+v), so p≥u+v/3.
Using these facts, the last displayed equation yields

    (f)≤(3-2/3+1-)(u+v)-b
    =u+v/3-b.

Combining this with the assumption (f)>1-2D/3-
we get u+v> 1-2D-3+3b.
Note that u+v≤ a+b
and b=f(a)≥ Da
imply that b ≥D/D+1(u+v). Combining these facts, we conclude that

    u+v> 1-2D-3+3b ≥ 1-2D-3 + 3D/D+1(u+v),

which implies (using also that D<1/2) the claim.


The following proposition provides a global quantitative estimate for functions f:[0,1]→ for which (f) is close to the maximum possible value.

Fix D∈[0,1/3], ∈(0,1/21] and let
f:[0,1]→ be a 1-Lipschitz function
such that f(0)=0, f(x)≥ Dx on [0,1] and
(f) > 1-2D/3-.
Let

    t_1= 1+D/3 - (1+D/1-2D-(1-D)).


Then

    x-3(1-D)  <      f(x)  ≤ x      on   [0,t_1] 
    
      t_1-3(1-D)  <      f(x)
                  on   [t_1,2t_1-6(1-D)]     and
    
      3t_1-x-3(1-D)  <      f(x)  <  1+D-x + 31-D/1-2D     on  [2t_1,1].




Let b=min_[1/2,1] f and choose a∈[1/2,1] such that
f(a)=b.
Then it is easy to see that (f)=(f|[0,a]).
So combining the assumption (f) > 1-2D/3-
and Proposition <ref> for f|[0,a] and C=1,
and then using b=f(a)≥ Da,
we get

    1-2D/3- < (f) =(f|[0,a]) ≤(a-b)(1-2D)/3(1-D)≤ a1-2D/3.

This implies


    a> 1-3/1-2D


and so

    a+b≥ a+Da > 1 + D - 31+D/1-2D.

By (<ref>),

    a-b> 1-D -31-D/1-2D.

Since f is 1-Lipschitz this implies that

    f(1)≤ b+1-a< D+31-D/1-2D,

which (using again that f is 1-Lipschitz) yields the upper estimate of
(<ref>) on [0,1].

By definition we have min_[1/2,a]f=f(a)=b, but
in order to apply our lemmas to f|[0,a] we have to show
min_[a/2,a]f=f(a).
Suppose then that min_[a/2,a]f<f(a). Then there exists an a'∈[a/2,1/2)
  such that  min_[a/2,a]f=f(a'). Using Proposition <ref>
applied to f|[0,a'] and C=1  we get
  
    1-2D/3- < (f) =(f|[0,a])=(f|[0,a'])
      ≤ a' 1-2D/3≤1/2·1-2D/3,

  which is impossible, since we assumed D≤ 1/3 and ≤ 1/21.


Therefore (<ref>) holds for f|[0,a].
Note that (<ref>) implies that t_0> t_1,
where t_0=a+b/3+δ(1-D) (as in Lemma <ref>).

By (<ref>), D≤ 1/3 and ≤ 1/21,
we get a>4/7, so <a/3 holds.
Then applying Lemmas <ref> and <ref> to
f|[0,a] and using that f is 1-Lipschitz
we get the lower estimate
of (<ref>) and (<ref>). The upper estimate
of (<ref>) is clear.

It remains to prove the lower estimate of
(<ref>).
Lemma <ref> (for f|[0,a]) gives that
every point of the graph of f|(a/2,a] must be above
either the y=1+D-x-31+D/1-2D line, or the
y=x/2-3(1-D) line.
These two lines intersect at (2t_1,t_1-3(1-D)). On the other hand, a calculation using ≤ 1/21, D≤ 1/3,
 a≤ 1 and (<ref>)

shows that a/2≤ 1/2 < 2t_1 ≤ 1-3/1-2D< a. We deduce that f(2t_1)> t_1-3(1-D).
Using the 1-Lipschitz property of f, this gives
the lower estimate of (<ref>).



  Let D∈[0,1/3], and let
f:[0,1]→ be a 1-Lipschitz function
  such that f(0)=0, f(x)≥ Dx on [0,1]
  and (f)≥1-2D/3.
Letting δ→ 0^+ in Proposition <ref>, we get
that f(x)=x on [0,1+D/3],
  f(x)≥1+D/3 on [1+D/3, 2(1+D)/3],
  and f(x)=1+D-x on [2(1+D)/3,1].
  It is easy to see that, conversely, (f)=1-2D/3 for any such f.
  Recall that by the C=1 special case of Proposition <ref>,
  we have  (f)≤1-2D/3 for any
  1-Lipschitz function f:[0,1]→
  such that f(0)=0, f(x)≥ Dx on [0,1].
  Therefore the above observation gives a characterization of those
  functions for which we have equality in Proposition <ref> when C=1.


The following corollary can be seen as a version of Proposition <ref> that is closer to the kind of estimates we will need in the proof of Theorem <ref>.

Let D∈[0,1/3) and

    Λ(D)=(1+D)(37-50D+60D^2)/18(3-4D+5D^2)≥Λ(0)=37/54=0.6851851….

Then there exist η>0 and
ξ∈(2/3,1] (depending continuously on D)
such that Λ(D)=ξ(1-2η) and the following holds.

If f:[0,1]→ is a 1-Lipschitz function such that
f(0)=0 and f(x)≥ Dx on [0,1] then

    (f) > 1-Λ(D)   ⟹   f(x) ≥x/3-ηξ on  [0,ξ].




  Let
  
    =(1+D)(1-2D)/18(3-4D+5D^2)∈(0,1/36).

  Then 1-Λ(D)=1-2D/3-. Let t_1 be the number given by Proposition <ref>. By the hypothesis (f)> 1-Λ(D),
  Proposition <ref> implies that (<ref>),  (<ref>)
  and (<ref>) hold.

  Let
  
    ξ   =3/4((1-3D)+1+D-31+D/1-2D) =
      (1+D)(13-20D+24D^2)/6(3-4D+5D^2)∈ (2/3,1),
    η   =δ(1-3D)/ξ=
      (1-2D)(1-3D)/3(13-20D+24D^2)>0.

  Then the three lines y=x-3(1-D), y=x/3-ηξ and y=Dx meet
  at (3,3D). Thus, since D<1/3, on [0,3] we have
  f(x)≥ Dx≥ x/3-ηξ and, using (<ref>), on [3,t_1] we have
  f(x) ≥ x-3(1-D) ≥ x/3-ηξ.

  One can also check that the lines y= x/3-ηξ and
  y=3t_1-x-3(1-D) intersect at x=ξ.
  Thus, by (<ref>), on [2t_1,ξ] we also have
  f(x) > 3t_1-x-3(1-D) ≥  x/3-ηξ.

It remains to check f(x)≥ x/3-ηξ on
[t_1,2t_1].
By (<ref>), f(2t_1)> t_1-3δ(1-D).
Hence (<ref>) and the 1-Lipschitz property
of f imply that on [t_1,2t_1] we have
f(x)> g(x)-3δ(1-D), where

    g(x)= 
       t_1     on  [t_1,2t_1-6(1-D)] 
    
       3t_1 -6(1-D) -x     on  [2t_1-6(1-D),2t_1-3(1-D)] 
    
       x-t_1     on  [2t_1-3(1-D),2t_1]
         .


Now we claim that

    g(x_0)-3δ(1-D) ≥ x_0/3-ηξ,     where  x_0=2t_1-3(1-D).

Indeed, using the definition of g and x_0 and
the equation ηξ=(1-3D), we obtain that the
left-hand side of (<ref>) is
t_1 - 6 (1-D), the right-hand side is
2t_1/3 - (2-4D), so it is enough to prove that
t_1/3 ≥(4-2D).
It is straightforward
to check that this last inequality follows
from the definition (<ref>) of t_1, D∈[0,1/3)
and ∈(0,1/36).

Note that the function g(x)-3(1-D) has slope
0 or -1 on [t_1,x_0] and it has slope 1 on
[x_0,2t_1], while x/3-ηξ has slope 1/3.
Thus (<ref>) implies that
g(x)-3δ(1-D) ≥ x/3-ηξ on [t_1,2t_1],
which completes the proof.





 §.§ Total drop for τ-good partitions


In this subsection we show that for small τ,
allowing only τ-good partitions
(recall Definition <ref>) does not change
too much the smallest possible total drop, see
Corollary <ref> below.
We begin with a lemma that will allow us to obtain τ-good partitions from partitions that satisfy a weaker property, with a controlled change in the total  drop.


Let f:[0,a]→ be a 1-Lipschitz function and
(a_n) be a good partition of [0,a].
Suppose that τ>0, K>1 is an integer,
(1+τ)^K<2 and
a_n-K/a_n≥ 2 for every n≥ K.
Then

    _τ(f) < (f,(a_n)) + 6K(K-1) τ a .




Fix i∈_0 and consider the numbers β_j=a_iK+j-1/a_iK+j (j=1,…,K).
Then β_1⋯β_K=a_iK/a_iK+K≥ 2 and for every j we have 1<β_j≤ 2. The goal is to make every β_j at least 1+τ so that each of them remains at most 2, the product β_1⋯β_K stays fixed, and the numbers a_iK+j are changed by only a small amount.

So let β'_j=1+τ if β_j≤ 1+τ, and to get the remaining
β'_j's decrease some of the corresponding β_j's (and choose β'_j=β_j for the rest), so that still β'_j≥ 1+τ and β'_1⋯β'_K=β_1⋯β_K; this is possible since (1+τ)^K<2.
Then
 let a'_iK=a_iK and
for each j=1,…, K

let a'_iK+j=a_iK/(β'_1⋯β'_j). Note

that
 a'_iK+K=a_iK+K,
1+τ≤ a'_iK+j-1/a'_iK+j≤ 2 for every j=1,…,K
and each a_iK+j was multiplied by a factor between (1+τ)^-K and (1+τ)^K to get a'_iK+j. This implies that for every j=1,…,K-1,

    |a'_iK+j-a_iK+j|≤ a_iK ((1+τ)^K-1) ≤
      2(a_iK-a_(i+1)K)((1+τ)^K-1).



Note that (a'_n)_n=0^∞ obtained by applying this procedure for every
i∈_0

is a τ-good partition of [0,a].

Let τ_0=2^1/K-1. Since (1+x)^K-1/x is increasing on (0,∞) (being a polynomial with positive coefficients) and
(1+τ)^K< 2, we have

    (1+τ)^K-1/τ<
    (1+τ_0)^K-1/τ_0=
    1/2^1/K-1≤K/ln 2<3K/2,

where we used the inequality
e^t-1 ≥ t.

Thus

    (1+τ)^K-1< 3Kτ/2.

Combining this with (<ref>)
 and a'_iK=a_iK, then

adding up, we get

    ∑_n=0^∞|a'_n-a_n| <
      (∑_i=0^∞(K-1)· 2(a_iK-a_(i+1)K)
                        3Kτ/2) 
    
      = (K-1)(a_0-lim_n→∞a_n)· 3Kτ
      =   3K(K-1)τ a.

Since f is 1-Lipschitz, changing one a_n by η
can change (f,(a_n)) by at most 2η, so the above inequality
implies

    (f,(a'_n))< (f,(a_n)) + 6K(K-1) τ a,

which completes the proof of the lemma.


The next lemma shows that we can replace an arbitrary good partition by one satisfying the assumptions of Lemma <ref>, without increasing the total drop.


For any >0 and
1-Lipschitz function f:[0,a]→
there exists a good  partition (a'_n) such that
a'_n-3/a'_n > 2 for every n≥ 3 and
(f,(a'_n))≤(f)+δ.



It is enough to show that
for any good partition (a_n)
there exists a good  partition (a'_n) such that
a'_n-3/a'_n > 2 for every n≥ 3 and
(f,(a'_n))≤(f,(a_n)).

First we claim that we can suppose that every interval
[a_n,a_n-1] is increasing or decreasing
(recall Definition <ref>).
Indeed, for each n≥ 1
if on the interval [a_n,a_n-1] the minimum of f is
taken at p∈(a_n,a_n-1) then inserting p to the partition
(in between a_n-1 and a_n) we get a new good partition
such that [a_n,p] is decreasing and [p,a_n-1] is increasing and
it is easy to see that (f,(a_n)) is not changed.

Suppose that a_n-2/a_n<2 (n≥ 2).
If [a_n,a_n-1] and [a_n-1,a_n-2] are both increasing
or both decreasing,  then by merging these intervals we get an interval of the same type,
and (f,(a_n)) remains unchanged.
If [a_n,a_n-1] is increasing and [a_n-1,a_n-2]
is decreasing then after merging the two intervals
the minimum of f on [a_n,a_n-2] is still
achieved at one of the endpoints of the interval,
and  (f,(a_n)) does not increase.

Applying the above merging procedure inductively (starting with n=2) whenever possible, we get a good partition (a'_n) such that
whenever a'_n-2/a'_n<2 (n≥ 2) then [a'_n,a'_n-1] is decreasing and [a'_n-1,a'_n-2]
is increasing. Since this cannot happen for both n and
n-1 we get that a'_n-2/a'_n≥ 2 or
a'_n-3/a'_n-1≥ 2 for any n≥ 3, which clearly
implies that a'_n-3/a'_n> 2.



For any 1-Lipschitz function f:[0,a]→ and
any 0<τ<1,

    _τ(f)≤(f) + 36 τ a.




Note that for any 1-Lipschitz function f:[0,a]→
and any partition (a_n) of [0,a], by definition, we have
0≤(f,(a_n))≤ a.
Thus the claim  holds trivially if
τ≥ 3  2 - 1.
Otherwise we can apply Lemma <ref>, and then
Lemma <ref> (for K=3).







 §.§ Discretizing the estimates



Recall from Definition <ref> the notion of τ-good partition of an integer interval (0,ℓ], and the notation (σ,(N_i)). Sometimes we refer to these as integer partitions for emphasis. Note that the requirement
(<ref>)
for a τ-good integer partition slightly
differs from the requirement
1+τ≤ a_k-1/a_k ≤ 2 for a τ-good
partition (see Definition <ref>), which
is equivalent to τ a_k ≤ a_k-1-a_k≤ a_k.
These two notions are connected by the following
lemma.


  Assume that L≤ℓ are positive integers.  Let f:[0,L/ℓ]→ be a 1-Lipschitz function and let (a_n) be a
  (2τ)-good partition of [0,L/ℓ].
  Then there exists a τ-good integer partition
  0=N_0<…<N_q=L of (0,L] such that
  
    ∑_j=0^q-1 f(N_j/ℓ)-min_[N_j/ℓ,N_j+1/ℓ] f ≤(f,(a_n))
      +O_τ(logℓ/ℓ).




Let N_0<…<N_q be the values taken by the sequence
  ⌊ℓ a_n ⌋. Since a_n→ 0 we get N_0=0. Thus 0=N_0<…<N_q=L is an integer partition of (0,L].

Using that (a_n) is a good partition we get

    ⌊ℓ a_n ⌋≤ℓ a_n ≤ 2 ℓ a_n+1 <
    2⌊ℓ a_n+1⌋ + 2,

hence ⌊ℓ a_n ⌋ - ⌊ℓ a_n+1⌋≤⌊ℓ a_n+1⌋ + 1.
Thus to prove that (N_j) is a τ-good integer partition of (0,L]
it is enough to show that
⌊ℓ a_n ⌋ - ⌊ℓ a_n+1⌋≥τ⌊ℓ a_n+1⌋ if
⌊ℓ a_n ⌋ > ⌊ℓ a_n+1⌋.
This is clear if τ⌊ℓ a_n+1⌋≤ 1.
Otherwise, using also that (a_n) is a (2τ)-good partition, we get

    ⌊ℓ a_n ⌋ - ⌊ℓ a_n+1⌋ >
    ℓ a_n - ℓ a_n+1 - 1
    ≥ 2τℓ a_n+1 - 1 ≥
    2τ⌊ℓ a_n+1⌋ -1
    > τ⌊ℓ a_n+1⌋.




Let K=max{ n: ℓ a_n ≥ 1}. Since (a_n) is (2τ)-good and ℓ a_0=L,
(1+2τ)^K≤ L≤ℓ, and so K≤logℓ /log(1+2τ).
Let a'_n=⌊ℓ a_n ⌋ / ℓ.
Since f is 1-Lipschitz
and |a'_n - a_n|<1/ ℓ,
we deduce that

    ∑_n=1^K+1 f(a'_n)-min_[a'_n,a'_n-1]f
    ≤∑_n=1^K+1(f(a_n)-min_[a_n,a_n-1]f + 2/ℓ) ≤(f,(a_n)) + 2(K+1)/ℓ.


By definition ℓ a_K+1<1,
hence a'_K+1=0.
Thus

    ∑_j=0^q-1 f(N_j/ℓ)-
         min_[N_j/ℓ,N_j+1/ℓ] f =
    ∑_n=1^K+1 f(a'_n)-
         min_[a'_n,a'_n-1]f
    ≤(f,(a_n)) +O_τ(logℓ /ℓ),

which completes the proof.


The following lemma will help us translate the results for Lipschitz functions to results for [-1,1]-sequences.

Let γ,Γ∈[-1,1], τ∈(0,1/2),
ζ∈(0,1) and
let σ∈ [-1,1]^ℓ satisfy

    γ j - ζℓ≤σ_1 +… + σ_j ≤Γ j + ζℓ   (1≤ j≤ℓ).


Then there exists a piecewise linear 1-Lipschitz
function f:[0,1]→ such that


  * 
f(j/ℓ)=1/ℓ(σ_1+…+σ_j)
if √(ζ)ℓ≤ j ≤ℓ,

  * 
    (γ-√(ζ)) x ≤ f(x) ≤
       (Γ +√(ζ)) x on [0,1] and

  * 
  for any integer 0<L≤ℓ,

    1/ℓ_τ(σ|(0,L]) ≤(f|[0,L/ℓ])
    +2√(ζ)+ 144τ + O_τ(logℓ /ℓ).





Let f_1:[0,1]→ be the piecewise linear function which is linear on each interval [j/ℓ,(j+1)/ℓ], and at the points j/ℓ takes the values

    f_1(j/ℓ) = 1/ℓ(σ_1+…+σ_j)
         (j=0,1,…,ℓ).

Since σ_i∈ [-1,1], this is a 1-Lipschitz function. Moreover, it follows from the assumption on σ that

    γ x - ζ≤ f_1(x) ≤Γ x + ζ  
    (x∈[0,1]),

and so

    (γ - √(ζ))x ≤
    f_1(x) ≤ (Γ + √(ζ))x
       for  x∈ [√(ζ),1].

Let f agree with f_1
on [√(ζ),1], f(0)=0 and let f be
linear on [0,√(ζ)].
Then f:[0,1]→ is also a piecewise linear 1-Lipschitz function and (<ref>) and
(<ref>) hold.

Therefore it remains to prove (<ref>).
Let 0<L≤ℓ be an integer.
By Corollary <ref> we have
_2τ(f)≤(f)+72τ.
Thus it is enough to show that for any
>0 and
(2τ)-good partition (a_n) of [0,L/ℓ]
there exists a τ-good
integer partition 𝒫 of σ|(0,L] such
that

    1/ℓ(σ|(0,L], 𝒫) ≤(f|[0,L/ℓ], (a_n)) + 2√(ζ)+ 72τ +
    O_τ(logℓ / ℓ)
     +.


Let N be the largest index such that
a_N≥√(ζ).
Then a_N≤ 2a_N+1 < 2√(ζ).
By applying Corollary <ref> and
Proposition <ref> to
f_1|[0,a_N]
with D=-1 and C=1,
we get

    _2τ(f_1|[0,a_N])
    ≤(f_1|[0,a_N]) + 72τ≤(a_N-f(a_N))· 3/6 + 72τ≤ 2√(ζ)+ 72τ.

Hence for any δ>0 there exists a
a (2τ)-good partition (b_n)
of [0,a_N] such that
(f_1|[0,a_N],(b_n))≤ 2√(ζ)+ 72τ + δ.

Let a'_n=a_n if n≤ N and a'_n=b_n-N
otherwise.
Then (a'_n)
is a (2τ)-good partition of [0,L/ℓ]
such that

    (f_1|[0,L/ℓ],(a'_n))≤(f|[0,L/ℓ], (a_n))
    +2√(ζ)+ 72τ + δ.


Applying Lemma <ref> for f_1|[0,L/ℓ]
and the (2τ)-good partition (a'_n) of [0,L/ℓ],
we get a τ-good integer partition
0=N_0<…<N_q=L of (0,L] such that

    ∑_j=0^q-1 f_1(N_j/ℓ)-min_[N_j/ℓ,N_j+1/ℓ] f_1 ≤(f_1|[0,L/ℓ],(a_n'))
      +O_τ(logℓ/ℓ).

Noting that the left-hand side of the above
expression is exactly
1/ℓ(σ,(N_j)),
and the right-hand side is at most the right-hand side
of (<ref>) by (<ref>),
the proof is complete.


The next proposition is a version of Proposition <ref> for sequences, and will play a central role in the proof of Theorem <ref>.
 
For any γ,Γ∈ [-1,1],
τ∈ (0,1/2), ζ∈(0,1) such that γ≤Γ and 2γ≤Γ, the following holds.

Let σ∈ [-1,1]^ℓ satisfy

    γ j - ζℓ≤σ_1 +… + σ_j ≤Γ j + ζℓ  (1≤ j≤ℓ).

Then

    1/ℓ_τ(σ) ≤(1-γ)(Γ-2γ)/1+2Γ-3γ
    +14√(ζ)
    + 144τ + O_τ(logℓ/ℓ).



Let f be the function provided by
Lemma <ref>.
Applying Proposition <ref> to
f with D=max(-1,γ-√(ζ)),
C=min(1,Γ+√(ζ)),
and using that D∈ [γ-√(ζ),γ] and C∈ [Γ,Γ+√(ζ)],
then using that 1+2Γ-3γ≥ 1, γ,Γ∈[-1,1] and ζ∈(0,1),
we obtain

    (f)    ≤(1-γ+√(ζ))
          (Γ-2γ+3√(ζ))/1+2Γ-3γ
       ≤(1-γ)(Γ-2γ)/1+2Γ-3γ
    +12√(ζ).

By applying (<ref>) of Lemma <ref> for L=ℓ
we get the desired inequality.



The following proposition will be used (only) in the proof of Theorem <ref>; it is essentially a consequence of Proposition <ref>,
 
For any γ, τ∈ (0,1/2),
ζ∈ (0,γ^2], δ>0  there is η=η(δ,γ)>0 such that the following holds
for any positive integer ℓ.


Let σ∈ [-1,1]^ℓ satisfy

    γ j - ζℓ≤σ_1 +… + σ_j    (1≤ j≤ℓ).


Then there exists an integer L∈ [ηℓ,ℓ] such that

    1/L_τ(σ|(0,L]) ≤Φ(γ)
    +1/η(O(√(ζ)) + O(τ) + O_τ(logℓ / ℓ) ) +δ.

where

    Φ(x)=2-x-√(3-3x^2)/4.




Let f be the function provided by
Lemma <ref> for Γ=1.
Choose δ∈(0,1/2) such that δ(2-4logδ)<δ
and let η=3Φ(γ)2^-1/δ>0.

Let  D=γ-√(ζ)≥ 0. Note that Φ is decreasing on [0,1/2], so
3Φ(D)2^-1/δ≥ 3Φ(γ)2^-1/δ = η. Using this
and applying Proposition <ref>,
we obtain a u∈[η,1] such that

    1/u(f|[0,u])     <    Φ(D)+δ =
    2-D-√(3-3D^2)/4 + δ
       ≤   2-(γ-√(ζ))-√(3-3γ^2)/4  +δ
    = Φ(γ)+√(ζ)/4 +δ.



Let L be the smallest integer such that u≤ L/ℓ.
Then clearly L∈[ηℓ, ℓ].

It is easy to see that for any 1-Lipschitz function
g:[0,a]→ and any 0<u_1<u_2≤ a we have
(g|[0,u_2])≤(g|[0,u_1]) + (u_2-u_1).
Thus

    1/u(f|[0,L/ℓ]) ≤1/u((f|[0,u])+1/ℓ)
    ≤Φ(γ)+√(ζ)/4 +δ+1/ℓ u.

Combining this with (<ref>) of Lemma <ref>,
we conclude

    1/L_τ(σ|(0,L])
       ≤1/u·1/ℓ_τ(σ|(0,L]) 
       ≤1/u((f|[0,L/ℓ]) + 2√(ζ)+ 144τ + O_τ(logℓ / ℓ) ) 
       ≤Φ(γ)+√(ζ)/4 +δ+1/ℓη
    +1/η( 2√(ζ)+ 144τ + O_τ(logℓ / ℓ) ) 
       ≤Φ(γ) +1/η(O(√(ζ)) + O(τ) + O_τ(logℓ / ℓ) ) +δ.



Finally, we get a version for sequences and integer partitions of Corollary <ref>, which will be applied to prove Theorem <ref>.
 
Let τ∈(0,1/2), γ∈ (0,1/3), ζ∈(0,γ^2) and

    Λ(x) = (1+x)(37-50x+60x^2)/18(3-4x+5x^2)     (x∈ [0,1/3]).

Then there exist η>0,ξ∈ (2/3,1] (depending on γ-√(ζ))
such that

    ξ (1-2η)  = Λ(γ-√(ζ))≥Λ(γ)-√(ζ)

and the following holds:

For any sequence (σ_1,…,σ_ℓ) ∈ [-1,1]^ℓ such that

    σ_1+ … +σ_j ≥γ j - ζℓ     (j=1,…,ℓ),

one of the following alternatives is satisfied:


  * 
    1/ξℓmax_j=1^ξℓ∑_i=1^j (1/3-σ_i) ≤η + 2√(ζ).


  * 
    1/ℓ_τ(σ) ≤ 1- Λ(γ)
    +3√(ζ)+ 144τ + O_τ(logℓ /ℓ).





We begin by noting that Λ(γ-√(ζ))≥Λ(γ)-√(ζ) since Λ'(x)≤ 1 on [0,1/3].

Let η>0,ξ∈ (2/3,1] be the numbers given in Corollary <ref> for D=γ-√(ζ)∈ (0,1/3). Suppose that (i) is false, so there is a
j≤ξℓ such that

    1/ξℓ∑_i=1^j
    (1/3-σ_i) > η +
    2√(ζ),

and therefore

    1/ℓ(σ_1+…+σ_j) <
    j/3ℓ - ηξ
    - 2 ξ√(ζ).

Note that the left-hand side is at least -j/ℓ and that, since η>0 and ξ≥ 2/3, we have
3/4(η+2√(ζ))ξ > √(ζ). This implies that j/ℓ > √(ζ).


Let f be the function provided by
Lemma <ref> for Γ=1,
and let x_0=j/ℓ.
Then x_0∈ [√(ζ),ξ] and
f:[0,1]→ is a 1-Lipschitz function
such that f(0)=0, f(x)≥ (γ-√(ζ))x
on [0,1], f(x_0)<x_0/3 - ηξ
- 2ξ√(ζ)≤ x_0/3-ηξ,
and

    1/ℓ_τ(σ) ≤(f)
    +2√(ζ)+ 144τ + O_τ(logℓ /ℓ).

Applying Corollary <ref> to
f, we get

    (f) ≤ 1-Λ(γ-√(ζ)) ≤ 1- Λ(γ)+√(ζ).

Combining this with (<ref>) we obtain (ii),
which completes the proof.







§ PROOFS OF MAIN THEOREMS





 §.§ Proof of Theorem <ref>



In this section we prove Theorem <ref>. Write

    ψ(s,u)= s(2+u-2s)/2+2u-3s,

and recall that χ(s,u)=min(ψ(s,u),1) for 0≤ s≤ u≤ 2 and s<2, and moreover χ(s,u)=1 if and only if u≤ 2s-1 (which forces s≥ 1).

The next proposition encapsulates some preliminary reductions towards the proof of Theorem <ref>. We first explain how to deduce the theorem from the proposition; the rest of the section is then devoted to the proof of the proposition.
 
For every 0<s≤ u≤ 2 with u>2s-1, the following holds.

Let μ∈([0,1)^2) satisfy _s(μ)<∞ and ((μ))≤ u.  If B⊂ [0,1)^2 is a compact set disjoint from (μ) with (B)>min(1,2-s), then

    sup_y∈ B(Δ_y (μ)) ≥ψ(s,u).





We proceed by contradiction. Assume, then,  that there exists a Borel set A⊂^2 such that 0< s≤(A)≤(A)≤ u≤ 2 and

    { y∈^2 : (Δ_y A) < χ(s,u) } > max(1,2-s).

By countable stability of Hausdorff dimension, there are η>0 and a set B⊂^2 with (B)>max(1,2-s) such that

    (Δ_y A) < χ(s,u) -η  for all y∈ B.

Since (Δ_y A) does not increase if we replace A by any subset, every Borel set of dimension s>0 contains compact subsets of positive s'-dimensional Hausdorff measure for all 0<s'<s, and χ(s,u) is continuous, at the price of replacing η by η/2 we may assume that  in (<ref>) the set A is compact and of positive s-dimensional Hausdorff measure. In turn, a routine verification shows that if A is compact, then the set

    { y: (Δ_y A) < χ(s,u)-η/2   }

is Borel. Hence in (<ref>) we may also assume that B is Borel.

Recall that χ(s,u)= 1 if and only if  u≤ 2s-1 (and s≥ 1 in this case). Hence, if u≤ 2s-1, then we can pick 0< s'≤ u'≤ 2 such that u'≥ u, 1≤ s'≤ s, u'>2s'-1, and ψ(s',u')>1-η/2. This shows that in (<ref>), we may further assume that u>2s-1 and replace χ(s,u) by ψ(s,u) (with η/2 in place of η).

Let μ∈(^2) be an s-Frostman measure on A, i.e. μ is a Radon measure supported on A and μ(B(x,r)) ≤ C r^s for all x∈^2, r>0, where C is independent of x (recall that we assumed that A has positive s-dimensional Hausdorff measure). By assumption, ((μ)) ≤ u. Using that packing dimension is equal to the modified upper box counting dimension (see e.g. <cit.>), and that (A_0)=(A_0), we see that for every δ>0 there is a compact set A_0⊂ A of positive μ-measure such that (A_0)≤min(u+δ,2).

We can then find disjoint compact subsets B'⊂ B, A'⊂ A_0 such that still μ(A')>0, (B')>max(1,2-s). Then (provided δ was taken small enough in terms of s,u,η)

    (Δ_y A') < ψ(s-δ,min(u+δ,2)) - η/2   for all y∈ B'.

This inequality is preserved under (joint) scaling and translation of μ, A',B', so it holds in particular for some compact A', B'⊂ [0,1)^2.  Since μ_A'(B(x,r)) ≤ C' r^s for some constant C'>0, we can check that _s-δ(μ_A')<∞. Since (μ_A')⊂ A', this contradicts Proposition <ref> applied to μ_A' and B', with s-δ, min(u+δ,2) in place of s, u (provided δ was taken small enough in terms of s,u,(B')).



In order to bound the Hausdorff dimension of Δ_y A from below, we will use the following standard criterion; although it is well known, we include the short proof for completeness.
 
Let F⊂^d be a Borel set and let ρ∈(^d) give full mass to F. Suppose that there are M_0∈_≥ 2 and s>0 such that for any M≥ M_0 and any Borel subset F'⊂ F with ρ(F')> M^-2, the number (F',M) of cubes in _M hitting F' is at least 2^s T M. Then ℋ^s(F)≳_T,d 1 and in particular (F)≥ s.


Let { B(x_i,r_i)} be a cover of F where r_i ≤ 2^-T M_0 for all i. Our goal is to estimate ∑_i r_i^s from below.

Write F_M for the union of all the B(x_i,r_i) for which 2^- T(M+1)≤ r_i ≤ 2^-TM. Pigeonholing, there is M≥ M_0 such that ρ(F_M)> M^-2. By assumption, one needs at least 2^sTM cubes in _M to cover F_M. It follows that the number of balls making up F_M is ≳_d,T 2^sTM, so that ∑_i r_i^s ≳_d,T 2^s T M  2^-s T M=1. This gives the claim.



We now begin the proof of Proposition <ref>. Since μ, s,u are fixed, any (possibly implicit) constants appearing in the proof may depend on them. Let ν be a measure supported on B with finite u'-energy where u'>max(1,2-s).  Let κ=κ(μ,ν)>0 be the number given by Proposition <ref>. We will show that (under the assumptions of the proposition) there exists y∈ B (possibly depending on T,,τ) such that

    (Δ_y ((μ))) > ψ(s,u) - o_T,,τ(1).

Recall that o_T,,τ(1) stands for a function of T,,τ which tends to 0 as T→∞ and ,τ→ 0^+. We will henceforth assume that T,,τ are given, and that the integer ℓ_0 is chosen large enough in terms of T,,τ so that all the claimed inequalities hold. As a first instance of this, apply Lemma <ref> to get  that

    |”_ℓ_0(μ,x)|    ≤κ for all  x∈_𝖽(μ)

provided ℓ_0 was taken large enough (in terms of T,,τ).

One can easily check that, given ν∈([0,1)^2) and j,k∈, the set  { (x,θ): θ∈(ν,x,j,k)} is Borel (recall Definition <ref>). It follows that the set

    Θ = { (x,θ): x∈_𝖽(μ), θ∈”_ℓ_0(μ,x) }

is Borel. Hence, applying Proposition <ref>, and using Fubini and the fact that μ is a Radon measure, we obtain a compact set A_1⊂_𝖽(μ)⊂(μ) with μ(A_1)>2/3 and a point y∈(ν)⊂ B such that

    P_y(x) ∉”_ℓ_0(μ,x)  for all  x∈ A_1.

Making  smaller (in terms of (B,(μ)) only) and ℓ_0 larger, we may assume that

    (B,A_1) ≥ + √(2)· 2^-ℓ_0.

We will show that, in fact, (Δ_y(A_1))≥ψ(s,u)-o_T,,τ(1), which clearly implies (<ref>). To do this, our aim is to apply Lemma <ref> with F=Δ_y(A_1), ρ=Δ_y(μ_A_1).  Note that if ρ(F')≥ℓ^-2, then A_2=Δ_y^-1(F') satisfies that μ_A_1(A_2)=ρ(F')≥ℓ^-2. Hence, in order to complete the proof of Proposition <ref>, it is enough to establish the following.

Claim. If the Borel set A_2⊂ [0,1)^2 satisfies μ_A_1(A_2) ≥ℓ^-2 with ℓ≥ℓ_0, where ℓ_0 is taken sufficiently large in terms of T,,τ, then

    log(Δ_y A_2,ℓ) ≥ (ψ(s,u)-o_T,,τ(1))Tℓ.


Fix, then, A_2 as above. Since the set Δ_y(R_ℓ A_2) is contained in the (√(2)· 2^-Tℓ)-neighborhood of Δ_y A_2, the numbers log(Δ_y A_2,ℓ) and log(Δ_y  R_ℓ A_2,ℓ) differ by at most a constant. Hence we can, and do, assume that A_2=R_ℓ A_2 from now on. Moreover, we may assume that A_2⊂ R_ℓ(A_1), since whenever A_2=R_ℓ A_2 and μ_A_1(A_2) ≥ℓ^-2, the same holds for A_2 ∩ R_ℓ(A_1).

Consider the sets given by Corollary <ref> applied to R_ℓμ. Applying the corollary with A=A_2, and using that

    2^- Tℓ≪23ℓ^-2≤μ(A_1)μ_A_1(A_2) ≤μ(A_2)=R_ℓμ(A_2)

for large enough ℓ, we can find a further 2^-Tℓ-set X such that, setting ρ=(R_ℓμ)_X,


  * ρ(A_2) ≥ℓ^-2/2.

  * R_ℓμ(X) ≥ 2^-o_T,(1) Tℓ and therefore, using that _s(R_ℓμ) ≲_T _s(μ) by  Lemma <ref>,

    _s(ρ) ≤ (R_ℓμ(X))^-2_s(R_ℓμ) ≲_T 2^o_T,(1) Tℓ_s(μ) ≲ 2^o_T,(1) Tℓ.


  * ρ is σ-regular for some sequence σ=(σ_1,…,σ_ℓ), σ_j∈ [-1,1].

  * X is contained in R_ℓ_𝖽(μ).




By Lemma <ref> and (ii), (iii) above,  and assuming that ℓ_0 was taken large enough in terms of T, we have

    ∑_i=1^j σ_i ≥ (s-1)j - ℓ o_T,(1)     (j=1,…,ℓ).

On the other hand, we have assumed that ((μ))≤ u, so that 𝒩((μ),j) ≤ O_(1) 2^(u+)T j for all j∈. By (iv) above, this also holds for X in place (μ) if j≤ℓ. On the other hand, using that ρ is σ-regular as in (<ref>), we get

    𝒩(X,j) = |_j(ρ)| ≥ 2^T(σ_1+1)⋯ 2^T(σ_j+1)   (1≤ j≤ℓ).

Combining these estimates, we deduce that 2^T(σ_1+…+σ_j+j)≤  O_(1) 2^(u+)T j, and hence

    ∑_i=1^j σ_i  ≤O_(1)/T + (u-1+)j ≤
    (u-1)j+ℓ o_T, (1)      (j=1,…,ℓ),

provided ℓ_0 was taken large enough in terms of .

Combining (<ref>) and (<ref>), we see that the assumptions of Proposition <ref> are satisfied with γ=s-1, Γ=u-1, and ζ=o_T,(1). After another short calculation, and starting with ℓ_0 large enough in terms of τ, we deduce that

    1/ℓ_τ(σ) ≤  1 - ψ(s,u) + o_T,,τ(1).


Recall from (<ref>) that if x∈  A_1, then θ(x,y)∉”_ℓ_0(μ,x). Hence, according to the definition of the sets '_ℓ_0ℓ(R_ℓμ,x) and ”_ℓ_0(μ,x) in (<ref>) and (<ref>) respectively, we have θ(x,y)∉'_ℓℓ(R_ℓμ,x)=_ℓℓ(ρ,x) for all x∈ A_1∩ X. Since we have assumed that A_2⊂ R_ℓ(A_1), the hypotheses of Proposition <ref> are met by ρ and A_2, with β= (the separation assumption follows from (<ref>)). Recalling (i), we see that if ℓ_0 was taken even larger in terms of T,,τ we can make the error term in Proposition <ref> equal to o_T,,τ(1). In light of  (<ref>), Proposition <ref> gives exactly (<ref>).

This completes the proof of the claim and, with it, of Proposition <ref> and Theorem <ref>.



 §.§ Proof of Theorem <ref>



In this section we prove Theorem <ref>. The proof goes along the same lines as the proof of Theorem <ref>, except that we rely on Proposition <ref> instead of Proposition <ref> to choose the scales in the multi-scale decomposition. The need to deal with two different scales 2^-TL and 2^-Tℓ also creates some additional challenges. Write

    ψ(s) = 1+s+√(3s(2-s))/4.

(This should not be confused with the function ψ(s,u) from <ref>.) The next proposition contains the core of Theorem <ref>. 

 
For every 1<s<3/2, the following holds.

Let μ∈([0,1)^2) satisfy _s(μ)<∞.  If B⊂ [0,1)^2 is a compact set disjoint from (μ) with (B)>1, then

    sup_y∈ B(Δ_y (μ)) ≥ψ(s).





Reasoning as in the deduction of Theorem <ref> from Proposition <ref>, we get that if U is a Borel subset of ^2 with (U)≥ t∈ (1,3/2), then

    { y∈^2: (Δ_y(U)) < ψ(t) }≤ 1.

The reason we need to go via box dimension is that the map y↦Δ_y(U) is Borel if U is compact, while it is unclear whether the map y↦Δ_y(U) is Borel, since it was proved in <cit.> that packing dimension is not a Borel function of the set if one considers the Hausdorff metric on the compact subsets of .

Now suppose the claim of Theorem <ref> does not hold. Then we can find a Borel set A⊂^2 with (A)=s∈ (1,3/2) and η>0 such that

    { y∈^2: (Δ_y(A)) < ψ (s)-η} > 1.

Let ν a Frostman measure on A of exponent t∈ (1,s), sufficiently close to s that ψ(t)≥ψ(s)-η, and note that

    { y∈^2: (Δ_y((ν))) < ψ (t) } > 1.

Fix a countable basis (U_i) of open sets of (ν) (in the relative topology). Note that (U_i) ≥ t for all i since ν is a Frostman measure. Hence, from (<ref>) we get that (E)≤ 1, where

    E = { y ∈^2: (Δ_y(U_i)) < ψ(t)  for some  i}.

Fix y∈^2∖ E. Let (F_j) be a countable cover of Δ_y((ν)). By Baire's Theorem, some Δ_y^-1(F_j) has nonempty interior in (ν), and hence contains some U_i. By the definition of E,

    (F_j) = (F_j) ≥(Δ_y(U_i)) ≥ψ(t).

By the characterization of packing dimension as modified upper box counting dimension (<cit.>), we conclude that (Δ_y((ν)) ≥ψ(t) whenever y∈^2∖ E. Since (E)≤ 1, this contradicts (<ref>), finishing the proof.


We now start the proof of Proposition <ref>. Let ν be a measure supported on B with finite u-energy for some u>1, and let κ=κ(μ,ν)>0 be the number given by Proposition <ref>.  Apply Lemma <ref> to obtain the bound

    |”_ℓ_0(μ,x)|    ≤κ for all  x∈_𝖽(μ)

provided ℓ_0 was taken large enough in terms of T,,τ. Recall that the set Θ in Equation (<ref>) is Borel. Applying Proposition <ref> to Θ and Fubini, we obtain a compact set A⊂_𝖽(μ) with μ(A)> 2/3 and a point y∈ B such that

    P_y(x) ∉”_ℓ_0(μ,x)  for all  x∈ A.


Fix a number δ>0. We will show that

    (Δ_y A) ≥ψ(s)- _T,,τ(δ),

where _T,,τ(δ) can be made arbitrarily small by first taking δ small enough, and then taking T large enough and ,τ small enough, all in terms of δ. This error term may also depend on s.

Fix a large integer ℓ≫ℓ_0. We claim that it is enough to find a scale L∈ [ℓ_0,ℓ], tending to infinity with ℓ, such that

    log𝒩(Δ_y(R_L A),L)/TL≥ψ(s) - _T,,τ(δ),

where the error term has property detailed above. Indeed, since Δ_y(R_L A) is contained in the O(2^-TL)-neighborhood of Δ_y(A), this implies the corresponding lower bound for (Δ_y(A)).

Apply Corollary <ref> to R_ℓμ.  Taking ℓ large enough that 2^- Tℓ≪ 2/3<μ(A)≤μ(R_ℓ A), there is a 2^-Tℓ-set X  such that, setting ρ=(R_ℓμ)_X,


  * ρ(R_ℓ A) ≥ 1/2.

  * R_ℓμ(X)   ≥ 2^-o_T,(1) Tℓ whence, as we saw in the proof of Proposition <ref>,

    _s(ρ) ≲_T 2^o_T,(1) Tℓ.


  * ρ is σ-regular for some sequence σ=(σ_1,…,σ_ℓ), σ_j∈ [-1,1].

Note that, provided ℓ_0 was taken large enough, (<ref>) still holds, since it only depends on (ii) and (iii). We are then in the setting of Proposition <ref> with γ=s-1, ζ=o_T,(1). Let η=η(δ,s-1)>0 be the number given by the proposition; we underline that, since δ is chosen before T,,τ, the number η is also independent of T,,τ (it is useful to keep in mind that η does depend on δ). A short calculation shows that 1-ψ(s)=Φ(s-1). From now we assume that ℓ is taken large enough (in terms of δ and s) that ηℓ≥ℓ_0. Then, applying Proposition <ref> and making ℓ even larger, we get an integer L ∈ [ηℓ,ℓ]⊂ [ℓ_0,ℓ] such that

    1/L_τ(σ|(0,L]) ≤ 1-ψ(s) + η^-1 o_T,,τ(1) +δ.


Note that R_Lρ is (σ_1,…,σ_L)-regular. Also, if x∈ A∩ X, then

    θ(x,y)    ∉'_ℓℓ(R_ℓμ,x)    (by (<ref>) and (<ref>))
        = _ℓℓ(ρ,x)    (by  (<ref>), since X came from Cor. <ref>)
       ⊃_(/η) L L(ρ,x)    (by Def.  <ref>, ℓ≤ (/η)L and L≤ℓ)
        = _(/η) L L(R_Lρ,x)    (by Def.  <ref>).

Note that x↦_(/η) L L(R_L ρ,x) is constant on each square of _L(R_Lρ). Hence, for each x∈ R_L(A∩ X) there is x∈ A∩ X⊂ R_L(A∩ X) such that θ(x,y)∉_(/η)L L(R_Lρ,x). Assume <η. If  was taken small enough and ℓ  large enough that (B,(μ))≥ +  √(2)· 2^-ℓ_0, then all the hypotheses of Proposition <ref> are satisfied for R_Lρ, R_L(A∩  X) and L in place of ρ, A and ℓ, with β=/η. Using (i) above (which implies R_Lρ(R_L A) ≥ 1/2) and the bound L≥ηℓ, the error term in Proposition <ref> can be bounded by

    2/η +  o_T,(1) + O_T,,τ(log^2(ηℓ)/ηℓ) .

Making ℓ large enough in terms of T,,τ,δ and s, this error term can be made o_T,(1)+2η^-1. Hence Proposition <ref> together with (<ref>) ensure that (<ref>) holds, with the error behaving as claimed.

Since L≥ηℓ and ℓ is arbitrarily large, L is also arbitrarily large. Hence we have shown that (<ref>) holds for arbitrarily large L and, as explained above, this completes the proof of Proposition <ref> and, with it, of Theorem <ref>.




 §.§ Proof of Theorem <ref>


In this section we prove Theorem <ref>. Throughout this section, we let Δ:^4→, (x,y)↦ |x-y|. We start by recalling a more quantitative version of the Mattila-Wolff bound (<ref>).

 
Suppose μ_1,μ_2∈([0,1)^2) have -separated supports. If _4/3(μ_1)<+∞, _4/3+(μ_2)<∞, then Δ(μ_1×μ_2) has an L^2 density, and

    Δ(μ_1×μ_2)_2^2  ≲__4/3(μ_1) _4/3+(μ_2).



Given μ∈([0,1)^2), let

    σ(μ,r)    = ∫_S^1 |μ(θ r)|^2  dθ,
    σ_α(μ)    = sup{ r^ασ(μ,r) : r> 0 }.

Mattila <cit.> proved that

    Δ(μ_1×μ_2)_2^2 ≲__α(μ_1) σ_2-α(μ_2).

We remark that in <cit.> this is proved for a weighted version of the distance measure (see <cit.>), but the weight u^-1/2 lies in the interval [(√(2))^-1/2, ^-1/2] by our assumption that the supports of μ_1,μ_2 are -separated and contained in [0,1)^2. Later Wolff <cit.> proved that for any μ∈([0,1)^2),

    σ_β/2(μ) ≲_β,_β+(μ),

and this is sharp up to the  when β∈ (1,2). See also <cit.> for an exposition of these arguments. Combining these estimates with α=β=4/3 yields the claim.


In the proof we will also require the following well-known lemma, whose proof we include for completeness.
 
Let f∈ L^2() satisfy ∫ f dx=1. Then ((f),L) ≥ 2^T L/f_2^2 for all L∈.


Using Cauchy-Schwarz and Jensen's inequality, we estimate

    1    = ( ∑_I∈_L∫_I f )^2 
       ≤((f),L) ∑_I∈_L(∫_I f)^2 
       ≤((f),L) ∑_I∈_L 2^-T L∫_I f^2
       = 2^-T L((f),L) f_2^2.




 As usual fix T≫ 1, ,τ≪ 1. Let Λ(x) be the function defined in Proposition <ref>. A calculation shows that

    Λ(s-1) =s(147-170s+60s^2)/18(12-14s+5s^2).

As Λ is continuous, it is enough to show that if A⊂^2 is a Borel set with (A)>s, then (Δ(A× A))≥Λ(s-1). It is enough to consider the case in which A is bounded. After translating and rescaling A, we may further assume that A⊂ [0,1)^2.

Let μ_1,μ_2∈([0,1)^2) be measures supported on A such that _s(μ_1),_s(μ_2)<∞, and their supports are (2)-separated (making  smaller if needed). Any implicit constants arising in the proof may depend on μ_1, μ_2 and s.


Let κ_1,κ_2>0 be the numbers given by Proposition <ref> applied to μ_1,μ_2 and μ_2,μ_1 in place of μ,ν respectively, and set κ=min(κ_1,κ_2).

Pick ℓ_0 large enough in terms of T,,τ that, invoking Lemma <ref>,

    ”_ℓ_0(μ_i,x) ≤κ for all  x∈_𝖽(μ_i),   i=1,2.

Let

    Θ_i = { (x,θ): x∈_𝖽(μ_i), θ∈”_ℓ_0(μ_i,x)},    i=1,2.

Applying Proposition <ref> first with  μ_1,μ_2 and Θ_1 in place of μ,ν,Θ and then with μ_2,μ_1 and Θ_2 in place of μ,ν,Θ, we get that there exists a compact set G⊂_𝖽(μ_1)×_𝖽(μ_2) such that (μ_1×μ_2)(G)>1/3 and

    θ(x,y)∉”_ℓ_0(μ_1,x)  and  θ(y,x)∉”_ℓ_0(μ_2,y)  for all (x,y)∈ G.

We write μ=μ_1×μ_2 from now on. Denote s_0=Λ(s-1). Our goal is to show that

    (Δ(G)) ≥ s_0.

Since Δ(G)⊂Δ(A× A), this will establish the theorem. In turn, since a Borel set F'⊂ satisfies (Δμ_G)(F')> ℓ^-2 if and only if B=Δ^-1(F') satisfies μ_G(B)> ℓ^-2, according to Lemma <ref>, in order to complete the proof it is enough to prove the following claim.

Claim. The following holds if ℓ is large enough in terms of μ,T,,τ: if B is a Borel subset of [0,1)^2× [0,1)^2 such that μ_G(B) > ℓ^-2, then

    log(Δ(B),ℓ) ≥ Tℓ (s_0-o_T,,τ(1)).


We start the proof of the claim. Firstly, replacing B by a compact subset of almost the same measure we may assume that B is compact. We may assume also that B⊂ G. Note that μ(B) = μ_G(B)μ(G)≥ℓ^-2/3.

Let (X_k^(i))_k=1^N_i be the 2^-Tℓ-sets given by Corollary <ref> applied to  R_ℓ(μ_i). Note that we have a disjoint union

    _𝖽(R_ℓμ_i)= ( ⋃_k=1^N_i X_k^(i)) ∪X^(i),  where μ_i(X^(i)) =R_ℓμ_i(X^(i)) ≤ 2^- Tℓ.


Write ρ_k^(i) =  (R_ℓμ_i)_X_k^(i). Note that ρ_k^(i) is  σ_k^(i)-regular for some σ_k^(i)∈ [-1,1]^ℓ; in particular, it is a 2^-Tℓ-measure. Also, by Lemma <ref> and Corollary <ref>(ii), and using our assumption that _s(μ_i)<∞,

    _s(ρ_k^(i)) ≤(R_ℓμ_i(X_k^(i)))^-2_s(R_ℓμ_i) ≲_T 2^o_T,(1)Tℓ.

Hence, using Lemma <ref> and increasing the value of ℓ_0 again,  any σ=σ_k^(i) satisfies

    σ_1+…+σ_j ≥ (s-1)j - ζℓ    (j=1,…,ℓ),

where ζ=o_T,(1). By starting with appropriate T,, we may assume that ζ<(s-1)^2.

If ρ is σ-regular, we write

    (ρ) =  1 - 1/ℓ_τ(σ).

Let F_i⊂_𝖽(R_ℓμ_i) be union of the sets X_k^(i) over all k such that (ρ_k^(i))≥ s_0-δ, where

    δ = 3√(ζ) + 145τ.

Note that, since the X_k^(i) are 2^-Tℓ-sets, then so if F_i.

Consider two (non mutually exclusive) cases:


  * Either μ_B(F_1×^2)≥ 1/3 or μ_B(^2 × F_2)≥ 1/3 (or both).

  * μ_B((^2∖ F_1)× (^2∖ F_2))≥  1/3.

Roughly speaking, in the first case we will argue as in the proof of Theorem <ref>, while in case (b) we will appeal to Proposition <ref>.

Assume then that (a) holds. Without loss of generality, suppose μ_B(F_1×^2)≥ 1/3. Instead of showing that (<ref>) holds directly for B, we will show that it holds for the set

    B' = ⋃_y∈ [0,1) (R_ℓ B_y ×{y})

where, for the rest of this section, given A⊂^2×^2 we denote its “horizontal” sections by A_y = { x: (x,y)∈ A} (for y∈^2). In other words, to form B' we make each horizontal fiber of B into a union of squares in _ℓ. One can check that B' is Borel (in fact, σ-compact). Since B⊂ B'⊂ R_ℓ B, the numbers (Δ(B'),ℓ) and (Δ(B),ℓ) differ by at most a multiplicative constant so that proving (<ref>) for B' implies it also for B. Since we are assuming that B⊂ G, we have that B'⊂ G', where G' is defined analogously to B'.

Using Fubini, that F_1 = R_ℓ F_1, our definition of B', the assumption μ_B(F_1×^2)≥ 1/3, and the fact that μ(B)≥ℓ^-2/3, we get

    (R_ℓμ_1 ×μ_2) ((F_1×^2) ∩ B')    =
    ∫ R_ℓμ_1 (F_1 ∩ B'_y)  dμ_2 (y) 
       =
    ∫μ_1 (F_1 ∩ R_ℓ B_y)  dμ_2 (y) 
       =
    μ ( (F_1 ×^2) ∩ B' ) 
       ≥μ_B (F_1 ×^2) μ (B) ≥ℓ^-2 / 9.


Applying (<ref>) with i=1, we can decompose

    R_ℓμ_1 = (R_ℓμ_1)|_X^(1) + ∑_k=1^N_1μ_1(X_k^(1)) ρ_k^(1).

Hence, using that R_ℓμ_1(X^(1)) ≤ 2^- Tℓ and taking ℓ large enough, there exists k such that

    (ρ_k^(1)×μ_2)( (F_1×^2) ∩ B') ≥ℓ^-2/9 - 2^- Tℓ≥ℓ^-2/10.

By the definition of F_1, we must have (ρ_k^(1))≥ s_0-δ, and  _𝖽(ρ_k^(1))⊂ F_1. By Fubini, we can find y∈_𝖽(μ_2) such that

    ρ_k^(1) (B'_y) ≥ℓ^-2/10.

Since B'⊂ G'⊂ R_ℓ G, we know that if x∈ B'_y then there exists x∈_ℓ(x) such that (x,y)∈ G. By (<ref>), this implies that θ(x,y)∉”_ℓ_0(μ_1,x).  Recalling the definitions (<ref>), (<ref>), we have shown that the hypotheses of Proposition <ref> hold for ρ_k^(1) and B'_y, with β= (the separation between y and (ρ_k^(1)) follows from the fact that the supports of μ_1 and μ_2 are (2)-separated, making ℓ larger again). Recalling (<ref>), we see that the error term in Proposition <ref> can be made ≤ o_T,,τ(1) by making ℓ even larger.  Applying the proposition, and recalling that (ρ_k^(1)) ≥ s_0-δ, where δ=o_T,,τ(1) was defined in (<ref>), we conclude that (for this fixed value of y)

    log(Δ_y(B'_y),ℓ) ≥ Tℓ(s_0-o_T,,τ(1)),

and hence the same lower bound holds for log(Δ(B'),ℓ). This concludes the proof of the claim in case (a).

We now consider case (b). Since (Δ(B),ℓ) and (Δ(R_ℓ B),ℓ) differ by at most a multiplicative constant, it is enough to prove (<ref>) for R_ℓ B in place of B. It follows from  the assumption of case (b), the decomposition (<ref>) for both μ_1, μ_2,  and the definitions of the sets F_i that

    1/3μ(B)    ≤μ( ((^2∖ F_1)× (^2∖ F_2)) ∩ B)  
       ≤ 2· 2^- Tℓ + ∑_(k_1,k_2):(ρ_k_i^(i))<s_0-δ R_ℓμ_1(X_k_1^(1)) R_ℓμ_2(X_k_2^(2)) ( ρ_k_1^(1)×ρ_k_2^(2))(R_ℓ B)  .

Hence, using that μ(B)≥ℓ^-2/3, we can find k_1,k_2 such that (ρ_k_i^(i))<s_0-δ for i=1,2, and

    (ρ_k_1^(1)×ρ_k_2^(2))(R_ℓ B) ≥1/3μ(B) - 2· 2^- Tℓ≥1/10ℓ^-2,

if ℓ is large enough in terms of .

Write ρ_k_i^(i) = ρ'_i for simplicity. In light of (<ref>) and our earlier assumption ζ<(s-1)^2, the hypothesis of Proposition  <ref> holds for the sequences σ arising from both ρ'_1 and ρ'_2, with γ=s-1. Let η>0, ξ∈ (2/3,1] be the numbers given in the proposition (they depend on s-1-√(ζ)) . Since (ρ'_i)<Λ(s-1)-δ, where δ was defined in (<ref>), if we take ℓ sufficiently large, then the alternative (i) in Proposition <ref> must hold.

Let ρ”_i=R_⌊ξℓ⌋(ρ'_i). Note that if ρ'_i is (σ_1,…,σ_ℓ)-regular, then ρ”_i is (σ_1,…,σ_⌊ξℓ⌋)-regular.  Using Lemma <ref> (with ⌊ξℓ⌋ in place of ℓ), recalling that ζ=o_T,,τ(1) and that the alternative (i) in Proposition <ref> holds, and making ℓ larger if needed, we get

    log_4/3(ρ”_i) ≤ξ Tℓ(η+o_T,,τ(1))    (i=1,2).

On the other hand, we see from Lemma <ref> that

    _4/3+(ρ”_i) ≲_T, 2^ξ Tℓ_4/3(ρ”_i).

We apply Theorem <ref> (together with the last two displayed equations) to get

    Δ(ρ”_1×ρ”_2)_2^2     ≲_T, 2^ξ Tℓ_4/3(ρ”_1) _4/3(ρ”_2)
       ≤ 2^o_T,,τ(1) ξ Tℓ 2^2 ηξ Tℓ.

It follows from (<ref>) that (ρ”_1×ρ”_2)(R_⌊ξℓ⌋B)≥ℓ^-2/10. We deduce that, for ℓ large enough,

    logΔ( (ρ”_1 ×ρ”_2)_R_⌊ξℓ⌋B)_2^2  ≤ξ Tℓ(2η+o_T,,τ(1)).

Applying Lemma <ref> to f=Δ( (ρ”_1 ×ρ”_2)_R_⌊ξℓ⌋B) and L=⌊ξℓ⌋, we conclude that

    log(Δ(B),ℓ)    ≥log(Δ(B),⌊ξℓ⌋) 
       ≳log(Δ(R_⌊ξℓ⌋ B),⌊ξℓ⌋)
    ≥ξ Tℓ(1-2η-o_T,,τ(1))

for ℓ sufficiently large. Since ξ(1-2η)≥ s_0-√(ζ) by Proposition <ref> and ζ=o_T,,τ(1), this concludes the proof of case (b) of the claim, which completes the proof of Theorem <ref>.





§ SHARPNESS OF THE RESULTS




It is natural to ask what parts of our approach are sharp and which are not.  In this section we show that  the results of Section <ref> are sharp, up to error terms. Hence, if the main results are not sharp (which seems likely), this is not due to the estimates for _τ(σ), but rather to the fact that Proposition <ref> (which connects the value of _τ(σ) to the size of distance sets) is itself not sharp. 

We begin by showing that Proposition <ref> is sharp for
all parameter values (and even the value of f(a) can be chosen
as an arbitrary b∈[Da,Ca]). This is illustrated by the following functions.

First consider the case when C=1.
Let x_0=y_0=0,
x_1=y_1=y_2=(1+D)(a-b)/3(1-D),
x_2=2x_1,
x_3=a-b/1-D, y_3=Dx_3, x_4=a and y_4=b,
let f(x_i)=y_i (i=0,…,4) and let f be linear
on every interval [x_i-1,x_i].
(See Figure <ref> for D=0,
a=1 and b=0 and note that in the most important b=Da case x_3=x_4, so the graph consists of only
three linear segments.)
It is clear that
f(a)=b and
Dx≤ f(x) ≤  Cx
on [0,a].
It is easy to check that f is 1-Lipschitz.
The fact that the first inequality of (<ref>)
holds with equality (and for b=aD also the second one)
follows from the observation that the set of hard
points of f is [x_2,x_3]  (recall Definition <ref>),  Lemma <ref>, and a straightforward calculation.



Now we consider the case when C<1.
Let q=(1+D)(1-C)/(1-D)(2+C).
For k=0,1,… let

    x_3k=a-b/1-Cq^k,   
    x_3k+1=a-b/1-Dq^k,   
    x_3k+2=2x_3k+3,

y_3k=Cx_3k, y_3k+1=Dx_3k+1
and y_3k+2=y_3k+3.
Let f(0)=0, f(a)=b, f(x_j)=y_j (j=1,2,…)
and let f be linear on [x_1,a] and on each
[x_j+1,x_j].
(See Figure <ref> for a=1, b=D=0, C=(√(3)-1)/2, and for
a=1, b=D=1/7, C=4/7, and note again that
because of b=Da, the segment [x_1,a] is degenerated in both cases.)
Again, it is clear that
f(a)=b and
Cx≤ f(x) ≤ Dx on [0,a], and
it is easy to check that f is 1-Lipschitz.
Now, observing that the set of hard points is
∪_k=1^∞ [x_3k+2,x_3k+1],
Lemma <ref> and another straightforward calculation
show that indeed
(f)=(a-f(a))(C-2D)/1+2C-3D.



Proposition <ref>  is also sharp up to the error term:
  for any given
  D∈[0,1/2),
  we construct an f that satisfies
  the conditions and for which for any u∈(0,a] we have
  (f|[0,u])≥ uΦ(D).

  Recall that at the end of the proof of Proposition <ref> we claimed
 that (1-C)(C/2-D)/1+2C-3D≤Φ(D) on [2D,1].
 The function Φ(D) was of course chosen so that this
 is sharp, in fact for
 C=3D-1+√(3-3D^2)/2∈
 ( 2D, 1 )
 we have equality. Let C be chosen this way, and
 let f be the function we obtained above when we showed the sharpness of Proposition <ref> for these values of C and D.
 (See Figure <ref> for a=1, b=D=0, and for
a=1, b=D=1/7.)
 As it was already mentioned above,
 the set of hard points of f is
 ∪_k=1^∞ [x_3k+2,x_3k+1].
 By Lemma <ref>, this implies that if we
 want to minimize (f|[0,u]) / u, then u must be
 of the form u=x_3k+2.
 Lemma <ref> and a simple calculation shows
 that for every k we get

    (f|[0,x_3k+2])/x_3k+2=
    (1-C)(C/2-D)/1+2C-3D=Φ(D),

which establishes the claimed sharpness.


Now we show that the lower estimates in (<ref>) and (<ref>)
are sharp in Proposition <ref>: for any D∈[0,1/3] and
∈[0,1/12]
we construct 1-Lipschitz functions f_1 and f_2 on [0,1]
such that f_i(x)≥ Dx on [0,1], f_i(0)=0,
(f_i)=1-2D/3- (i=1,2),
f_1(x)=x-3(1-D) on [3,t_1] and
f_2(x)=3t_1-x-3(1-D) on [2t_1,1-3/1-2D],
where t_1 is given by (<ref>).

Let

    f_1(x) =
    min(x,3(1+D)-x)     on  [0,3] 
    min(x-3(1-D),1+D-x)     on  [3,1]
         .

Then f_1(x)≥ Dx on [0,1], and f_1(x)=x-3(1-D) on
[3,1+D/2+3(1-D)/2]⊃  [3,t_1]. One can check that set of hard points of f_1 is
[2(1+D),3]∪ [23(1+D+3(1-D)),1],
where ∈[0, 1/12] ensures that both intervals
have nonnegative length,
and so
Lemma <ref> gives that (f_1)=1-2D/3-.

Now, let

    f_2(x) =
    min(x,3t_1-x-3(1-D))     on  [0,1-3/1-2D] 
    
       Dx     on  [1-3/1-2D,1]
         .

Then f_2(x)≥ Dx on [0,1], and

    f_2(x)=3t_1-x-3(1-D)  on [3/2(t_1-(1-D)),1-3/1-2D]⊃[2t_1,1-3/1-2D].

After checking that the set of hard points of f_2 is
[2t_1-2(1-D),1-3/1-2D], Lemma <ref>  yields (f_2)=1-2D/3-.

We claim that Corollary <ref> is sharp in the following sense:
If D∈[0,0.26], η>0, ξ∈(0,1], Λ_1=ξ(1-2η) and
 for every 1-Lipschitz function f:[0,1]→ such that f(0)=0 and
 f(x)≥ Dx on [0,1] we have

    (f)≥ 1-Λ_1⟹ f(x) > x/3-ηξ on  [0,ξ],

 then Λ_1 < Λ(D).

Indeed, if η> 1/3-D then Λ_1=ξ(1-2η)< 1-2(1/3-D) = 1/3+2D, which
 is less than Λ(D) when D∈[0,0.26].

So we can suppose that η≤ 1/3-D.
Let x_1=ξ(4/3-η)/(1+D),
x_2=min(x_1,1) and

    f_3(x) =
    min(x,-x+
       x_2(1+D))     on 
      [0, x_2] 
    
       Dx     on  [ x_2,1]
         .

Then f_3 is 1-Lipschitz,
f_3(0)=0, f_3(x)≥ Dx on [0,1] and
f_3(x)=-x+
 x_2(1+D)
on [x_0, x_2], where


    x_0=x_21+D/2≤ x_11+D/2=
    ξ(2/3-η/2)<ξ.

It is easy to see that the set of hard points of f_3
is [2/3 x_2(1+D),x_2] and so by
Lemma <ref> we have (f_3)=x_2(1-2D)/3.
The assumptions η≤1/3-D
 and ξ≤ 1
imply that ξ≤ x_2, hence
ξ∈[x_0,x_2], and we have


    f_3(ξ)=-ξ+x_2(1+D)≤ -ξ+x_1(1+D)=ξ/3-ηξ.

Thus by our assumption (<ref>) we must have x_2(1-2D)/3=(f_3) < 1-Λ_1.
If x_1≥ 1 then x_2=1, so we obtain
Λ_1 < 2(1+D)/3.
It is easy to check that Λ(x)≥ 2(1+x)/3
on [0,1/2], so in this case we obtained
Λ_1 < Λ(D) as we claimed.
So we can suppose that x_1<1 and so x_2=x_1.
Then x_2(1-2D)/3 < 1-Λ_1 gives

    ξ(4/3-η)1-2D/3(1+D) < 1-ξ(1-2η).

Let

    =Λ_1-2/3(1+D)=ξ(1-2η)-2/3(1+D).

We can clearly suppose that
Λ_1≥Λ(D).
Since Λ(D)≥2/3(1+D), we obtain
≥ 0.
We also have ≤ 1/12 since this is clear
if ξ≤ 3/4 and follows from
(<ref>) and the assumption
η≤ 1/3-D if ξ>3/4.
For this value of  let f_1
be the 1-Lipschitz function defined above
(to show the sharpness of (<ref>) of Proposition <ref>).
Then f_1(0)=0, f_1(x)≥ Dx on [0,1] and
(f_1)=1-2D/3-=1-Λ_1, so by (<ref>) we must have
f_1(x)>x/3-ηξ on [0,ξ].
Since ξ≤ 1 and η>0 we have
3=3ξ(1-2η)-2(1+D)≤ 3ξ-2≤ξ. Thus we get f_1(3)>-ηξ.
Since f_1(3)=3 D this gives ηξ > (1-3D).


From the definition of  we get
ξ= + 2ηξ + 2/3(1+D).
Considering , ξ and ηξ as
variables and D as a parameter,
substituting the above expression into
(<ref>), and then using that
ηξ > (1-3D),
after some calculations one gets
< (1+D)(1-2D)/18(3-4D+5D^2), which yields
Λ_1=+2/3(1+D)<Λ(D), as we claimed.


We remark that if η=1/3-D, ξ=1,
Λ_1=ξ(1-2η)=1/3+2D then (<ref>) holds, since
then f(x)≥ Dx on [0,1] already implies that
 f(x)≥ x/3 - ηξ on [0,ξ]. So in order to make
 Corollary <ref> sharp for every D∈[0,1/3), the function Λ(D) has to
   replaced by max(Λ(D),1/3+2D), which is equal to Λ(D) if and
   only if D≤ 0.2609…. However, this version would not improve any of our distance set estimates.


Finally, we claim that Propositions <ref>,
<ref> and <ref>
are also sharp, up to the error terms.
Indeed, given a 1-Lipschitz function f:[0,1]→ and ℓ∈,
let σ=σ_f,ℓ∈ [-1,1]^ℓ be the sequence

    σ_i=ℓ(f(i/ℓ)-f((i-1)/ℓ)).

It is not hard to show that for any positive integer L≤ℓ and
good integer partition  of (0,L] there exists a good partition
(a_n) of [0,L/ℓ] such that
 (f|[0,L/ℓ],(a_n))≤1/ℓ(σ|(0,L],)+O(logℓ/ℓ),
   thus
   
    (f|[0,L/ℓ])≤1/ℓ_τ(σ|(0,L]) +O(logℓ/ℓ).

Thus, starting with the functions defined in this section that witness the
     sharpness of Propositions <ref> and <ref> and
     Corollary <ref>, this way we get sequences that show
     the sharpness of Propositions <ref>,
     <ref> and <ref>,
     up to the error terms.


plain



