Selberg sieve variational problem
From Polymath1Wiki
(→World records) |
(→World records) |
||
Line 460: | Line 460: | ||
| | | | ||
| | | | ||
- | | [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment- | + | | [http://terrytao.wordpress.com/2014/02/21/polymath8b-ix-large-quadratic-programs/#comment-297456 4.0043] |
| [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.6889] | | [http://terrytao.wordpress.com/2014/02/09/polymath8b-viii-time-to-start-writing-up-the-results/#comment-271610 4.6889] | ||
|- | |- |
Revision as of 16:55, 14 April 2014
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 DHL[k,m + 1] holds whenever EH[θ] holds and . Thus for instance, M_{k} > 2 implies DHL[k,2] on the Elliott-Halberstam conjecture, and M_{k} > 4 implies DHL[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 and a > 1 to be chosen later (in practice we take c close to 1 / logk, 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 r in the interval [1,1 + τ] and 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 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 logx 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
For Z_{2}, which is a tiny term, we use the crude bound
For Z_{1}, we use the bound
valid for any a > 1, which can be verified because the LHS is concave for , while the RHS is convex and is tangent to the LHS as x=a. We then have
and thus
where
A good choice for a = a[r] here is (assuming ), in which case the formula simplifies to
Thus far, our arguments have been valid for arbitrary functions g. We now specialise to functions of the form
Note the identity
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 logk) as S_{k − 1} approaches r. To deal with this issue we average in r, and specifically over the interval [1,1 + τ]. One can calculate that
for all x if we have (because the two expressions touch at x = 1 + τ, with the RHS being convex with slope at least (1 + τ / 2) / τ there. and the LHS lying underneath this tangent line). Assuming this, we conclude that
provided that kμ < 1 − τ, and hence
Now we deal with the Z_{4} integral. We split into two contributions, depending on whether or not. If , then we may bound
when , so this portion of may be bounded by
Observe that
and so this portion of is bounded by
- WX
where
As for the portion when 1 + uτ − S_{k − 1} > 2c, we bound , and so this portion of may be bounded by
- = VU
where
We thus arrive at the final bound
provided that kμ < 1 − τ and the denominator is positive.
Asymptotic analysis
We work in the asymptotic regime . Setting
for some absolute constants and β,γ > 0, one calculates
and so the constraint 1 − kμ > τ becomes
With for , one has
and one also calculates
- Z_{2},Z_{3} = o(1)
and hence
assuming that α + logβ − 1 > γ and
and where .
In particular, by setting α,β,γ as absolute constants obeying these constraints, we have , and so
- M_{k} = logk + O(1).
If we set c = τ: = 1 / logk, 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; one can check that all the terms in the numerator are 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 EH[θ] which controls more general Dirichlet convolutions than the von Mangoldt function (a precise assertion in this regard may be found in BFI). In fact (as shown here) one can 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). See this blog post for more discussion.
If the marginal distributions of F are supported in instead of , one still has a usable lower bound in which is replaced by the slightly smaller quantity ; see this blog post for more discussion.
World records
k | M_{k} | M'_{k} | M''_{k} (prism) | M''_{k} (symmetric) | M''_{k} (non-convex) | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1D | Lower | Upper | Lower | Upper | Lower | Upper | Lower | Upper | Lower | Upper | Lower | Upper | |
2 | 1.383 | 1.38593... | 1.38593... | 2 | 2 | 2 | 2 | 2 | 2 | 1.690608 | 2 | ||
3 | 1.635 | 1.64644 | 1.648 | 1.8429 | 2.080 | 1.914 | 2.38593... | 1.902626 | 3 | 1.847 | 3 | 1.87459 | 2.4142 |
4 | 1.820 | 1.845407 | 1.848 | 1.937 | 2.198 | 1.951 | 2.648 | 1.937 | 4 | 2.05411 | 2.5946 | ||
5 | 1.965 | 2.007145 | 2.011797 | 2.059 | 2.311 | 2.848 | 2.20264 | 2.7466 | |||||
10 | 2.409 | 2.54547 | 2.55842 | 2.7466 | 2.68235 | 3.2716 | |||||||
20 | 2.810 | 3.12756 | 3.1534 | 3.2716 | 3.21470 | 3.8564 | |||||||
30 | 3.015 | 3.48313 | 3.51848 | 3.6079 | 3.51943 | 4.2182 | |||||||
40 | 3.145 | 3.73919 | 3.783467 | 3.8564 | 3.71480 | 4.4815 | |||||||
50 | 3.236 | 3.93586 | 3.99186 | 4.0540 | 4.0043 | 4.6889 | |||||||
51 | 3.244 | 3.95304 | 4.0105 | 4.0717 | 4.011910 | 4.7075 | |||||||
53 | 3.259 | 3.986213 | 4.0466 | 4.1062 | 4.000161 | 4.744 | |||||||
54 | 3.266 | 4.00223 | 4.0642 | 4.1230 | |||||||||
55 | 3.273 | 4.01788 | 4.0816 | 4.1396 | |||||||||
59 | 3.299 | 4.07704 | 4.1478399 | 4.2030 |
k | (sym) | (prism) | (sym) | (non-convex) | (sym) | (sym) | (prism) | ||
---|---|---|---|---|---|---|---|---|---|
2 | 1.38593... | 2 | 2 | 2 | 2 | 1.690608 | 2 | ||
3 | 1.8615 | 1.956713 | 1.936708 | 1.962998 | 1.9400 | 1.87459 | 1.992 | 2.0012 | 1.965 |
4 | 2.0023 | 2.0023 | 2.0023 | 2.0023 | 2.05411 |
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). The 1D bound is the optimal value for M_{k} when the underlying function F is restricted to be of the "one-dimensional" form .
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 .
The quantity is defined as the supremum of where F is now supported on , and is defined as but now restricted to , and is a parameter to be optimised in. The quantity is defined similarly, but with F now supported on . Finally, is also defined similarly, but with F supported on a region R as above, with all marginals supported on .
The quantities are defined similarly to , but with the truncation of R to [0,1 / θ]^{k} removed.
For k=3, we also have the non-convex candidate .
The crude upper bound of k for any of the M_{k} type quantities comes from the parity problem obstruction that each separate event "n + h_{i} prime" can occur with probability at most 1/2.
Quantity | Polytope constraints | Vanishing marginals? | Epsilon trick? | Need GEH? |
---|---|---|---|---|
M_{k} | No | No | No | |
M'_{k} | for all j | No | No | Yes |
M''_{k} (prism) |
| Yes | No | Yes |
M''_{k} (symmetric) |
for all j | Yes | No | Yes |
M''_{3} (nonconvex)
(k,θ) = (3,1) | OR
OR
| Yes | No | Yes |
M''_{3} (nonconvex II)
(k,θ) = (3,1) | OR
OR ; AND ALSO
| Yes | No | Yes |
(symmetric) | Yes | No | Yes! | |
(prism) |
| Yes | No | Yes! |
for all j | No | Yes | Yes | |
(symmetric) | for all j
for all j | No | Yes | Yes |
(prism) |
| Yes | Yes | Yes |
(symmetric) |
for all j | Yes | Yes | Yes |
(non-convex)
(k,θ) = (3,1) | OR
OR
| Yes | Yes | Yes |
| No | Yes | Yes! | |
(symmetric) | for all j
| No | Yes | Yes! |
(symmetric) | Yes | Yes | Yes! |