# Selberg sieve variational problem

### From Polymath1Wiki

(→Lower bounds) |
(→Lower bounds) |
||

Line 34: | Line 34: | ||

== Lower bounds == | == Lower bounds == | ||

- | We will need some parameters <math>c, T, \tau > 0</math> to be chosen later (in practice we take c close to <math>1/\log k</math>, T a small | + | We will need some parameters <math>c, T, \tau > 0</math> to be chosen later (in practice we take c close to <math>1/\log k</math>, T a small multiple of c, and <math>\tau</math> a small multiple of c/k). |

For any symmetric function F on the simplex <math>{\mathcal R}_k</math>, one has | For any symmetric function F on the simplex <math>{\mathcal R}_k</math>, one has | ||

Line 130: | Line 130: | ||

If we have the pointwise bound | If we have the pointwise bound | ||

- | :<math> r \log_+ \frac{r-s}{T} + (r-s)_+ \frac{s}{kT} \leq C (s - s_0)^2</math> (*) | + | :<math> r \log_+ \frac{r-s}{T} + (r-s)_+ \frac{s}{kT} \leq C (s - s_0)^2 + C'</math> (*) |

- | for some <math>C, s_0 > 0</math> and all s, then we have | + | for some <math>C, C', s_0 > 0</math> and all s, then we have |

:<math>Z_1 + Z_2 \leq C {\mathbf E} (S_k - s_0)^2 </math> | :<math>Z_1 + Z_2 \leq C {\mathbf E} (S_k - s_0)^2 </math> | ||

- | :<math> = C ( (k \mu - s_0)^2 + k \sigma^2 )</math> | + | :<math> = C ( (k \mu - s_0)^2 + k \sigma^2 ) + C'</math> |

where | where | ||

Line 164: | Line 164: | ||

:<math>Y_2 \leq \frac{k}{k-1} Z_4</math> | :<math>Y_2 \leq \frac{k}{k-1} Z_4</math> | ||

- | where | + | where <math>Z_4 = Z_4[r]</math> is the quantity |

- | :<math>Z_4 := \frac{\log k}{m_2} {\mathbf E} (r - S_{k-1} - c)^2 \int_{[0,\min(r-S_{k-1},T)]} g(s)^2 | + | :<math>Z_4 := \frac{\log k}{m_2} {\mathbf E} (r - S_{k-1} - c)^2 \int_{[0,\min(r-S_{k-1},T)]} g(s)^2 h_r(s)\ ds.</math> |

Putting all this together, we have | Putting all this together, we have | ||

- | :<math> r \Delta_k {\mathbf P} ( S_k \leq r ) \leq \frac{k}{k-1} ( C ( (k \mu - s_0)^2 + k \sigma^2 ) + Z_3 + Z_4 ).</math> | + | :<math> r \Delta_k {\mathbf P} ( S_k \leq r ) \leq \frac{k}{k-1} ( C ( (k \mu - s_0)^2 + k \sigma^2 ) + C' + Z_3 + Z_4[r] ).</math> |

+ | |||

+ | At this point we encounter a technical problem that <math>Z_4</math> diverges logarithmically (up to a cap of <math>\log k</math>) as <math>S_{k-1}</math> approaches r. To deal with this issue we average in r, and specifically over the interval <math>[1,1+\tau]</math>. We assume that the pointwise bound (*) is valid for all r in this interval. If we have | ||

+ | |||

+ | :<math> \int_0^1 (1+a\tau) 1_{x > 1+a\tau}\ da \leq \delta (x-k\mu)^2</math> | ||

+ | |||

+ | for all x and some <math>\delta > 0</math>, then | ||

+ | |||

+ | :<math> \int_0^1 (1+a\tau) {\mathbf P} ( S_k \leq 1+a\tau )\ da \leq 1 + \frac{\tau}{2} - k \delta \sigma^2</math> | ||

+ | |||

+ | and hence | ||

+ | |||

+ | :<math> \Delta_k (1 + \frac{a\tau}{2} - k \delta \sigma^2) \leq \frac{k}{k-1} ( C ( (k \mu - s_0)^2 + k \sigma^2 ) + C' + Z_3 + \int_0^1 Z_4[1+a\tau]\ da ).</math> | ||

+ | |||

+ | If <math>\tau \leq c</math>, we may bound | ||

+ | |||

+ | :<math>\int_0^1 Z_4[1+a\tau]\ da := \frac{\log k}{m_2} {\mathbf E} ((1 - S_{k-1})^2 + c^2) \int_{[0,T)]} g(s)^2 (\int_0^1 h_{1+a\tau}(s) 1_{1+a\tau-S_{k-1} \geq s}\ da)\ ds.</math> | ||

+ | |||

+ | Observe that | ||

+ | |||

+ | :<math>\int_0^1 h_{1+a\tau}(s) 1_{1+a\tau-S_{k-1} \geq s}\ da = \int_0^1 \frac{da}{1-S_{k-1}+a\tau+(k-1)s} 1_{1-S_{k-1}+a\tau \geq s}</math> | ||

+ | :<math> = \frac{1}{\tau} \int_{[\max(ks, 1-S_{k-1}+(k-1)s), 1-S_{k-1}+\tau+(k-1)s]} \frac{du}{u}</math> | ||

+ | :<math> \leq \frac{1}{\tau} \log \frac{ks+\tau}{ks}</math> | ||

+ | |||

+ | and so | ||

+ | :<math>\int_0^1 Z_4[1+a\tau]\ da \leq W \frac{\log k}{\tau} {\mathbf E} ((1 - S_{k-1})^2 + c^2)</math> | ||

+ | |||

+ | :<math>= W \frac{\log k}{\tau} ((1 - (k-1)\mu)^2 + (k-1) \sigma^2 + c^2)</math> | ||

+ | |||

+ | where | ||

+ | |||

+ | :<math>W := m_2^{-1} \frac{1}{\tau} \int_{[0,T)]} g(s)^2 \log(1+\frac{\tau}{ks})\ ds.</math> | ||

+ | |||

+ | We thus arrive at the final bound | ||

+ | |||

+ | :<math> \Delta_k \leq \frac{k}{k-1} \frac{ C ( (k \mu - s_0)^2 + k \sigma^2 ) + C' + Z_3 + W \frac{\log k}{\tau} ((1 - (k-1)\mu)^2 + (k-1) \sigma^2 + c^2)}{1 + \frac{\tau}{2} - k \delta \sigma^2}</math> | ||

+ | |||

+ | provided that the denominator is positive. | ||

+ | |||

+ | If we set <math>c = \tau := 1/\log k</math>, with <math>T</math> a small multiple of c, then <math>\mu \approx \frac{1}{k}(1 - \frac{A}{\log k})</math> for a large absolute constant A, and <math>\sigma^2</math> is a small multiple of <math>\frac{1}{k \log^2 k}</math>. This makes the denominator comparable to 1; if we then set <math>s_0 = k \mu</math>, then one can check that (*) holds with <math>C = O(\log^2 k )</math> and <math>C' = O(1)</math>; also, <math>Z_3, W = O(1)</math>, finally giving the bound | ||

+ | |||

+ | :<math>\Delta_k = O(1)</math> | ||

- | + | and thus we have the lower bound | |

- | + | :<math>M_k \geq\frac{k}{k-1} \log k - O(1) = \log k - O(1)</math>. | |

== More general variational problems == | == More general variational problems == |

## Revision as of 04:16, 18 December 2013

Let *M*_{k} be the quantity

where *F* ranges over square-integrable functions on the simplex

with being the quadratic forms

and

It is known that *D**H**L*[*k*,*m* + 1] holds whenever *E**H*[θ] holds and . Thus for instance, *M*_{k} > 2 implies *D**H**L*[*k*,2] on the Elliott-Halberstam conjecture, and *M*_{k} > 4 implies *D**H**L*[*k*,2] unconditionally.

## Contents |

## Upper bounds

We have the upper bound

- (1)

that is proven as follows.

The key estimate is

- . (2)

Assuming this estimate, we may integrate in to conclude that

which symmetrises to

giving the desired upper bound (1).

It remains to prove (2). By Cauchy-Schwarz, it suffices to show that

But writing , the left-hand side evaluates to

as required.

## Lower bounds

We will need some parameters *c*,*T*,τ > 0 to be chosen later (in practice we take c close to 1 / log*k*, T a small multiple of c, and τ a small multiple of c/k).

For any symmetric function F on the simplex , one has

and so by scaling, if F is a symmetric function on the dilated simplex , one has

after adjusting the definition of the functionals suitably for this rescaled simplex.

Now let us apply this inequality to truncated tensor product functions

for some bounded measurable , not identically zero, with . We have the probabilistic interpretations

and

where , and are iid random variables in [0,T] with law , and we adopt the convention that

∫ | f |

[a,b] |

vanishes when *b* < *a*. We thus have

- (*)

for any r.

We now introduce the random function *h* = *h*_{r} by

Observe that if *S*_{k − 1} < *r*, then

and hence by the Legendre identity

We also note that (using the iid nature of the *X*_{i} to symmetrise)

Inserting these bounds into (*) and rearranging, we conclude that

where is the defect from the upper bound. Splitting the integrand into regions where s or t is larger than or less than T, we obtain

where

and

We now focus on *Y*_{1}. It is only non-zero when . Bounding , we see that

where log_{ + }(*x*) is equal to log*x* when and zero otherwise. We can rewrite this as

We write and . Using the bound we have

and thus (bounding .

- .

Symmetrising, we conclude that

where

If we have the pointwise bound

- (*)

for some *C*,*C*',*s*_{0} > 0 and all s, then we have

- =
*C*((*k*μ −*s*_{0})^{2}+*k*σ^{2}) +*C*'

where

Thus far, our arguments have been valid for arbitrary functions *g*. We now specialise to functions of the form

Note the identity

*g*(*t*) −*h*(*t*) = (*r*−*S*_{k − 1}−*c*)*g*(*t*)*h*(*t*)

on [0,min(*r* − *S*_{k − 1},*T*)]. Thus

Bounding and using symmetry, we conclude

Since , we conclude that

where *Z*_{4} = *Z*_{4}[*r*] is the quantity

Putting all this together, we have

At this point we encounter a technical problem that *Z*_{4} diverges logarithmically (up to a cap of log*k*) as *S*_{k − 1} approaches r. To deal with this issue we average in r, and specifically over the interval [1,1 + τ]. We assume that the pointwise bound (*) is valid for all r in this interval. If we have

for all x and some δ > 0, then

and hence

If , we may bound

Observe that

and so

where

We thus arrive at the final bound

provided that the denominator is positive.

If we set *c* = τ: = 1 / log*k*, with *T* a small multiple of c, then for a large absolute constant A, and σ^{2} is a small multiple of . This makes the denominator comparable to 1; if we then set *s*_{0} = *k*μ, then one can check that (*) holds with *C* = *O*(log^{2}*k*) and *C*' = *O*(1); also, *Z*_{3},*W* = *O*(1), finally giving the bound

- Δ
_{k}=*O*(1)

and thus we have the lower bound

- .

## More general variational problems

It appears that for the purposes of establish DHL type theorems, one can increase the range of F in which one is taking suprema over (and extending the range of integration in the definition of accordingly). Firstly, one can enlarge the simplex to the larger region

provided that one works with a generalisation of *E**H*[θ] which controls more general Dirichlet convolutions than the von Mangoldt function (a precise assertion in this regard may be found in BFI). In fact one should be able to work in any larger region *R* for which

provided that all the marginal distributions of F are supported on , thus (assuming F is symmetric)

- when

For instance, one can take , or one can take (although the latter option breaks the symmetry for F). Perhaps other choices are also possible.

## World records

k
| M_{k}
| M'_{k}
| M''_{k}
| |||
---|---|---|---|---|---|---|

Lower | Upper | Lower | Upper | Lower | Upper | |

2 | 1.38593... | 1.38593... | 2 | 2 | 2 | 2 |

3 | 1.646 | 1.648 | 1.842 | 2.080 | 1.917 | 2.38593... |

4 | 1.845 | 1.848 | 1.937 | 2.198 | 2.648 | |

5 | 2.001162 | 2.011797 | 2.059 | 2.311 | 2.848 | |

10 | 2.53 | 2.55842 | ||||

20 | 3.05 | 3.1534 | ||||

30 | 3.34 | 3.51848 | ||||

40 | 3.52 | 3.793466 | ||||

50 | 3.66 | 3.99186 | ||||

59 | 3.95608 | 4.1479398 |

For k>2, all upper bounds on *M*_{k} come from (1). Upper bounds on *M*'_{k} come from the inequality that follows from an averaging argument, and upper bounds on *M*''_{k} (on EH, using the prism as the domain) come from the inequality by comparing *M*''_{k} with a variational problem on the prism (details here).

For k=2, *M*'_{2} = *M*''_{2} = 2 can be computed exactly by taking F to be the indicator function of the unit square (for the lower bound), and by using Cauchy-Schwarz (for the upper bound). can be computed exactly as the solution to the equation .