VizualBusiness: A combinatorial subset sum problem associated with bounded prime gaps

A combinatorial subset sum problem associated with bounded prime gaps:
The purpose of this post is to isolate a combinatorial optimisation problem regarding subset sums; any improvement upon the current known bounds for this problem would lead to numerical improvements for the quantities pursued in the Polymath8 project.

First, some (rough) motivational background, omitting all the number-theoretic details and focusing on the combinatorics. (But readers who just want to see the combinatorial problem can skip the motivation and jump ahead to Lemma 5.) As part of the Polymath8 project we are trying to establish a certain estimate called ${MPZ[\varpi,\delta]}$ for as wide a range of ${\varpi,\delta > 0}$ as possible. Currently the best result we have is:

Theorem 1 ${MPZ[\varpi,\theta]}$ holds whenever ${207\varpi + 43\delta< \frac{1}{4}}$ .

Enlarging this region would lead to a better value of certain parameters ${k_0}$ , {H}

which in turn control the best bound on asymptotic gaps between consecutive primes. See this previous post for more discussion of this. At present, the best value ${k_0=26,024}$ of ${k_0}$ is applied by taking ${(\varpi,\delta)}$ sufficiently close to {(1/964,17/20726)}

, so improving Theorem 1 in the neighbourhood of this value is particularly desirable.

I won’t state exactly what ${MPZ[\varpi,\theta]}$ is here (you can find a formulation in previous posts). But it involves a certain number-theoretic function, the von Mangoldt function ${\Lambda}$ . To prove the theorem, the first step is to use a certain identity (the Heath-Brown identity) to decompose ${\Lambda}$ into a lot of pieces, which take the form

$\displaystyle \alpha_{1} \ast \ldots \ast \alpha_{n} \ \ \ \ \ (1)$

for some bounded {n}

(in Zhang’s paper {n}

never exceeds {20}

) and various weights ${\alpha_{1},\ldots,\alpha_n}$ supported at various scales ${N_1,\ldots,N_n \geq 1}$ that multiply up to approximately {x}

$\displaystyle N_1 \ldots N_n \sim x.$

We can write ${N_i = x^{t_i}}$ , thus ignoring negligible errors, ${t_1,\ldots,t_n}$ are non-negative real numbers that add up to {1}

$\displaystyle t_1 + \ldots + t_n = 1.$

A key technical feature of the Heath-Brown identity is that the weight ${\alpha_i}$ associated to sufficiently large values of ${t_i}$ (e.g. ${t_i \geq 1/10}$ ) are “smooth” in a certain sense, but we will not detail this here (this is a subject for a subsequent post; actually, I may update the current post in the near future to add more specifics).
The operation ${\ast}$ is Dirichlet convolution, which is commutative and associative. We can thus regroup the convolution (1) in a number of ways. For instance, given any partition ${\{1,\ldots,n\} = S \cup T}$ into disjoint sets {S,T}

, we can rewrite (1) as

$\displaystyle \alpha_S \ast \alpha_T$

where ${\alpha_S}$ is the convolution of those ${\alpha_i}$ with ${i \in S}$ , and similarly for ${\alpha_T}$ .
Zhang’s argument splits into two major pieces, in which certain classes of (1) are established. Cheating a little bit, the following three results are established:

Theorem 2 (Type 0 estimate) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever

$\displaystyle t_i > \frac{1}{2} + 2 \varpi$
for some .

Theorem 3 (Type I/II estimate) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever one can find a partition ${\{1,\ldots,n\} = S \cup T}$ such that

$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma$
where ${\sigma}$ is a quantity such that

$\displaystyle 11 \varpi + 3\delta + 2 \sigma < \frac{1}{4}.$

Theorem 4 (Type III estimate) The term (1) gives an acceptable contribution to ${MPZ[\varpi,\delta]}$ whenever one can find distinct ${t_i,t_j,t_k}$ with

$\displaystyle t_i \leq t_j \leq t_k \leq \frac{1}{2}$
and

$\displaystyle 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta.$

The above assertions are oversimplifications; there are some additional minor smallness hypotheses on ${\varpi,\delta}$ that are needed but at the current (small) values of ${\varpi,\delta}$ under consideration they are not relevant and so will be omitted.

The deduction of Theorem 1 from Theorems 2, 3, 4 is then accomplished from the following, purely combinatorial, lemma:

Lemma 5 (Subset sum lemma) Let ${\varpi,\delta > 0}$ be such that

$\displaystyle 207\varpi + 43\delta< \frac{1}{4}. \ \ \ \ \ (2)$
Let ${t_1,\ldots,t_n}$ be non-negative reals such that

$\displaystyle t_1 + \ldots + t_n = 1.$
Then at least one of the following statements hold:

(Type 0) There is ${1 \leq i \leq n}$ such that ${t_i > \frac{1}{2} + 2 \varpi}$ .

(Type I/II) There is a partition ${\{1,\ldots,n\} = S \cup T}$ such that

$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma$
where ${\sigma}$ is a quantity such that

$\displaystyle 11 \varpi + 3\delta + 2 \sigma < \frac{1}{4}.$

(Type III) One can find distinct ${t_i,t_j,t_k}$ with

$\displaystyle t_i \leq t_j \leq t_k \leq \frac{1}{2}$
and

$\displaystyle 4t_k + 4t_j + 5t_i > 4 + 16 \varpi + \delta.$

The purely combinatorial question is whether the hypothesis (2) can be relaxed here to a weaker condition. This would allow us to improve the ranges for Theorem 1 (and hence for the values of ${k_0}$ and {H}

alluded to earlier) without needing further improvement on Theorems 2, 3, 4 (although such improvement is also going to be a focus of Polymath8 investigations in the future).

Let us review how this lemma is currently proven. The key sublemma is the following:

Lemma 6 Let ${1/10 < \sigma < 1/2}$ , and let ${t_1,\ldots,t_n}$ be non-negative numbers summing to . Then one of the following three statements hold:

(Type 0) There is a ${t_i}$ with ${t_i \geq 1/2 + \sigma}$ .

(Type I/II) There is a partition ${\{1,\ldots,n\} = S \cup T}$ such that

$\displaystyle \frac{1}{2} - \sigma < \sum_{i \in S} t_i \leq \sum_{i \in T} t_i < \frac{1}{2} + \sigma.$

(Type III) There exist distinct with ${2\sigma \leq t_i \leq t_j \leq t_k \leq 1/2-\sigma}$ and ${t_i+t_j,t_i+t_k,t_j+t_k \geq 1/2 + \sigma}$ .

Proof: Suppose Type I/II never occurs, then every partial sum ${\sum_{i \in S} t_i}$ is either “small” in the sense that it is less than or equal to ${1/2-\sigma}$ , or “large” in the sense that it is greater than or equal to ${1/2+\sigma}$ , since otherwise we would be in the Type I/II case either with {S}

as is and

the complement of {S}

, or vice versa.

Call a summand ${t_i}$ “useless” if it cannot be used to turn a small partial sum into a large partial sum, thus there are no ${S \subset \{1,\ldots,n\} \backslash \{i\}}$ such that ${\sum_{j \in S} t_j}$ is small and ${t_i + \sum_{j \in S} t_j}$ is large. We then split ${\{1,\ldots,n\} = A \cup B}$ where {A}

are the useless elements and {B}

are the useful elements.

By induction we see that if ${S \subset B}$ and ${\sum_{i \in S} t_i}$ is small, then ${\sum_{i \in S} t_i + \sum_{i \in A} t_i}$ is also small. Thus every sum of useful elements is either less than ${1/2-\sigma-\sum_{i \in A} t_i}$ or larger than ${1/2+\sigma}$ . Since a useful element must be able to convert a small sum to a large sum, we conclude that every useful element has size greater than ${2\sigma + \sum_{i \in A} t_i}$ . We may assume we are not in Type 0, then every useful element is at least ${2\sigma + \sum_{i \in A} t_i}$ and at most ${1/2 - \sigma - \sum_{i \in A} t_i}$ . In particular, there have to be at least three useful elements, otherwise ${\sum_{i=1}^n t_i}$ cannot be as large as 1. As ${\sigma > 1/10}$ , we have ${4\sigma > 1/2-\sigma}$ , and we conclude that the sum of any two useful elements is large. Taking ${t_i,t_j,t_k}$ to be three useful elements in increasing order we land in Type I/II. $\Box$
Now we see how Lemma 6 implies Lemma 5. Let ${\varpi,\delta}$ be as in Lemma 5. We take ${\sigma}$ almost as large as we can for the Type I/II case, thus we set

$\displaystyle \sigma := \frac{1}{8} - \frac{11}{2} \varpi - \frac{3}{2} \delta - \epsilon \ \ \ \ \ (3)$

for some sufficiently small ${\epsilon>0}$ . We observe from (2) that we certainly have

$\displaystyle \sigma > 2 \varpi$

and

$\displaystyle \sigma > \frac{1}{10}$

with plenty of room to spare. We then apply Lemma 5. The Type 0 case of that lemma then implies the Type 0 case of Lemma 6, while the Type I/II case of Lemma 5 also implies the Type I/II case of Lemma 6. Finally, suppose that we are in the Type III case of Lemma 5. Since

$\displaystyle 4t_i + 4t_j + 5 t_k = \frac{5}{2} (t_i+t_k) + \frac{5}{2}(t_j+t_k) + \frac{3}{2} (t_i+t_j)$

we thus have

$\displaystyle 4t_i + 4t_j + 5 t_k \geq \frac{13}{2} (\frac{1}{2}+\sigma)$

and so we will be done if

$\displaystyle \frac{13}{2} (\frac{1}{2}+\sigma) > 4 + 16 \varpi + \delta.$

Inserting (3) and taking ${\epsilon}$ small enough, it suffices to verify that

$\displaystyle \frac{13}{2} (\frac{1}{2}+\frac{1}{8} - \frac{11}{2} \varpi - \frac{3}{2}\delta) > 4 + 16 \varpi + \delta$

but after some computation this is equivalent to (2).
It seems that there is some slack in this computation; some of the conclusions of the Type III case of Lemma 5, in particular, ended up being “wasted”, and it is possible that one did not fully exploit all the partial sums that could be used to create a Type I/II situation. So there may be a way to make improvements through purely combinatorial arguments.

A technical remark: for the application to Theorem 1, it is possible to enforce a bound on the number {n}

of summands in Lemma 5. Mor precisely, we may assume that {n}

is an even number of size at most ${n \leq 2K}$ for any natural number {K}

we please, at the cost of adding the additioal constraint ${t_i > \frac{1}{K}}$ to the Type III conclusion. Since ${t_i}$ is already at least ${2\sigma}$ , which is at least ${\frac{1}{5}}$ , one can safely take {K=5}

, so

can be taken to be an even number of size at most {10}

, which in principle makes the problem of optimising Lemma 5 a fixed linear programming problem. (Zhang takes {K=10}

, but this appears to be overkill. On the other hand, {K}

does not appear to be a parameter that overly influences the final numerical bounds.)

Filed under: math.CO, math.NT, polymath Tagged: polymath8, subset sum, Yitang Zhang

DIGITAL JUICE

VizualBusiness

Tuesday, June 11, 2013

A combinatorial subset sum problem associated with bounded prime gaps

No comments:

Post a Comment

Digital Juice for Primary Education

About Me

Translate

Total Pageviews