Sequence Containment-Type Results

Let $P$ denote the sequence of primes and $A(a,d)$ denote the arithmetic progression with starting term $a$ and common difference $d$ . Dirichlet’s Theorem on Arithmetic progressions says that if $\gcd(a,d) = 1$ , then $A(a,d)$ contains infinitely many members of $P$ . But the Green-Tao Theorem says that for any $k$ , there exist $a,d$ such that $P$ contains $k$ members of $A(a,d)$ . In some sense, these results look like “inverses” of each other from the perspective of sequence containment: at a high level, given two sequences $S,T$ , one result talks about $S$ containing members of $T$ , and the other talks about $T$ containing members of $S$ .

Can we make this analogy a bit more precise?

When we write it out at a high level as we just did with $S,T$ , we might assume some level of symmetry to such “inverse” sequence containment results — we can use this to say something about the commutative operation of the intersection of $S$ and $T$ . But this doesn’t work directly with $P$ and $A$ since $A$ depends on $a,d$ — $A$ itself is actually a family of sequences, not just one.

But say we fix some $a,d$ , so that we can just talk about two sequences. Then, fixing $a,d$ such that $\gcd(a,d) = 1$ , Dirichlet’s theorem can be restated as saying that the intersection of $A(a,d)$ and $P$ is infinite. (We’re abusing notation by using the symbol to refer to both the sequence and the corresponding set, but there is no actual ambiguity here.) In full symbols, $\forall(a,d)\left( \gcd(a,d) = 1 \rightarrow \left| A(a,d) \cap P \right| = \infty \right)$ .

What does the Green-Tao theorem say instead? First off, we can’t state it while fixing $a,d$ , since the result involves existential quantification over these. So a restatement of it is that for any $k$ , there exist $a,d$ such that the intersection of $P$ and $A(a,d)$ is at least $k$ . In full symbols, $\forall k\left( \exists(a,d) \left| A(a,d) \cap P \right| \geq k \right)$ .

So with this perspective, these results are not actually really inverses, since both of them talk about the intersection, and either can be restated in terms of whichever sequence we want to be the “container.” For example, we can equivalently state Dirichlet’s Theorem as:

If $\gcd(a,d) = 1$ , then $A(a,d)$ contains infinitely many members of $P$
If $\gcd(a,d) = 1$ , then $P$ contains infinitely many members of $A(a,d)$

We have a similar ability to restate the Green-Tao theorem. In general, a theorem of the form “ $S$ contains $X$ many members of $T$ ” can be equivalently restated as “ $T$ contains $X$ many members of $S$ .” Thus, the “inverse” is not really accurate. Instead, both of these results basically place lower bounds on $\left| A(a,d) \cap P \right|$ , with differing conditions: Dirichlet’s theorem says that for all $a,d$ that are relatively prime the intersection is infinite, while the Green-Tao theorem says that for all $k$ there exist $a,d$ such that the intersection is at least size $k$ .

At a glance, Dirichlet’s theorem seems a bit stronger; however, the Green-Tao theorem was proven much more recently and was a massive breakthrough when it was published. But then I’m confused here: does the Green-Tao theorem not follow immediately from Dirichlet’s theorem? Namely, given $k$ , we can just pick any $a,d$ with $\gcd(a,d) = 1$ and we are given that … oh, this is where the difference lies. Dirichlet’s theorem implies that the intersection is infinite, but the Green-Tao theorem implies something different, that the intersection contains $k$ elements in order.

So my restatement of the Green-Tao theorem above is wrong. What would it be then? It would be that for all $k$ , there exist $a,d$ such that $P$ contains $k$ members of $A(a,d)$ in order. Does the order of how we mention the sequences matter? Yes, it does actually! Saying that $P$ contains $k$ members of $A(a,d)$ in order is very different from saying that $A(a,d)$ contains $k$ members of $P$ in order. So our restatement principle (for switching the sequences in a statement based on the commutativity of the set-theoretic intersection operation) doesn’t apply here.

Let’s add some symbolism to better exhibit the relationship between these kinds of results, as well as statements like the Twin Prime Conjecture (which feels a bit “arithmetic progression”-esque.) Let $S,T$ be two sequences. We say that $S \subseteq_{o,k}T$ if $T$ contains $k$ members of $S$ in order. If $T$ contains infinitely many members of $S$ in order, then we say that $S \subseteq_{o,\infty}T$ . If $T$ contains all of $S$ … well, then, that would actually be the same as (equivalent to) set-theoretic inclusion, so in that case we just write $S \subseteq T$ .

We can list some immediate facts here. We have chains of weaker to stronger statements:

$\displaystyle |S \cap T| \geq k \leftarrow S \subseteq_{o,k}T,$

$\displaystyle |S \cap T| = \infty \leftarrow S \subseteq_{o,\infty}T,$

$\displaystyle \exists k\left( S \subseteq_{o,k}T \right) \leftarrow \exists N(\forall k > N)\left( S \subseteq_{o,k}T \right) \leftrightarrow \forall k\left( S \subseteq_{o,k}T \right) \leftarrow S \subseteq_{o,\infty}T \leftarrow S \subseteq T.$

(The second statement is that for $k$ sufficiently large, $T$ contains $k$ members of $S$ in order. But this is actually equivalent to saying that for any $k$ , $T$ contains $k$ members of $S$ in order, since if $k < k^{'}$ and $T$ contains $k^{'}$ members of $S$ in order, then just picking a $k$ -length subsequence of these members automatically yields that $T$ contains $k$ members of $S$ in order too.)

Dirichlet’s theorem corresponds to $|S \cap T| = \infty$ , and the Green-Tao theorem corresponds to $\forall k\left( S \subseteq_{o,k}T \right)$ . The only (immediately noticeable) common generalization of these two is $S \subseteq_{o,\infty}T$ . But is this true?

Also, do we know anything about analogous questions with $T$ and $S$ flipped (where in our case, $S$ is the arithmetic progression and $T$ is the prime numbers)? Clearly Dirichlet’s theorem is symmetric, but what about the analogous statement for the Green-Tao theorem? Written out, this would be: for any $k$ , there exist $a,d$ such that the arithmetic progression with starting term $a$ and common difference $d$ contains $k$ primes in order.

This actually relates to questions like the Twin-Prime Conjecture! And probably the more general tuples conjecture too. (Note on terminology: I’ve seen this typically called the “ $k$ -tuples conjecture,” but given our different usage of the symbol $k$ we will just call this the tuples conjecture.) In fact, the statement applied to $k = 2$ would imply that there exist $a,d$ such that $A(a,d)$ contains two primes in order. The difference between these two primes would then have to be $d$ , and conversely if we exhibit two primes with difference $d$ then we can just pick $a$ to be the first prime and say that these two primes are $a,a + d$ . So this is equivalent to saying that there exist $a,d$ such that there exist two consecutive primes with difference $d$ . If we add back the “infinitely many” part to this statement, as seen in the Green-Tao theorem (it’s not just that $A(a,d) \subseteq_{o,k}P$ , it’s that there exist infinitely many such cases of $k$ elements of $A(a,d)$ in order), then we recover some of the biggest outstanding conjectures: if $d = 2$ then this is the Twin Prime Conjecture, while if say $d = 2k$ then this is a generalization of the Twin Prime Conjecture and a special case of the prime tuples conjecture. Actually, since the primes need to be consecutive, this is an even stronger version (generalization) of that special case of the prime tuples conjecture.

But hold on … this statement asserts existence of $d$ , so it doesn’t actually capture the Twin Prime Conjecture. In fact, that statement comes from $A(a,d) \subseteq_{o,k}P$ , not $P \subseteq_{o,k}A(a,d)$ . The difference between the Twin Prime Conjecture and the Green-Tao theorem comes from existence of $d$ versus for all $d$ . The Green-Tao theorem states that $\forall k$ , there exist infinitely many $(a,d)$ such that $A(a,d) \subseteq_{o,k}P$ . But the Twin Prime conjecture states that for $k = 2$ , and for specifically $d = 2$ , there exist infinitely many $a$ such that $A(a,d) \subseteq_{o,k}P$ . (Saying that $A(a,2) \subseteq_{o,2}P$ is the same as saying that there is some $l$ such that $a + 2l,a + 2l + 2$ are both prime. Requiring this for infinitely many $a$ is the same as saying that … actually, this is not the same, since $l$ is conditioned on $a$ . This statement is actually obviously true: if $a$ is any odd number, then choosing $l = \frac{3 - a}{2}$ , we have that $a + 2l,a + 2l + 2$ are both prime.) So actually, this statement is obvious and very much not equivalent to the Twin Prime Conjecture: for $k = 2$ and $d = 2$ , there exist infinitely many $a$ such that $A(a,d) \subseteq_{o,k}P$ .

How can we modify this slightly to rescue the coverage of outstanding conjectures like the Twin Prime Conjecture? And is the statement for other values of $k,d$ similarly trivial? In other words, is it true that: for any $k$ , and for any $d$ , there exist infinitely many $a$ such that $A(a,d) \subseteq_{o,k}P$ ? No, this is not obvious, since it would imply the Green-Tao theorem. What about for just $k = 2$ ? Can we recover the “trivial” proof then? In other words, is it true that: for any $d$ , there exist infinitely many $a$ such that $A(a,d) \subseteq_{o,2}P$ ? $A(a,d) \subseteq_{o,2}P$ is equivalent to saying that there exists $l$ such that $a + ld,a + (l + 1)d$ are both prime. But if $l$ is conditioned on $a$ , then we can probably trivially show this if we are given that for any possible gap there is a set of prime numbers for that gap. Actually, this is clearly false for $d$ odd; for example, if $d = 7$ , then the only possibility is that the first prime is 2, but that would imply the second prime is 9, which is not prime. So this is not true.

What about $A(a,d) \subseteq_{o,\infty}P$ ? How does that fit in to this? Is that known to be false?

First, as a sidenote, we immediately know that it is possible for $S \subseteq_{o,\infty}T$ while for no $k > 1$ does $T \subseteq_{o,k}S$ . (If $S \subseteq_{o,k}T$ for some $k$ , then at least for $k = 1$ trivially $T \subseteq_{o,1}S$ .) As an example, take $S$ as the sequence of even integers and $T$ as the sequence of all integers. Not even for $k = 2$ does $T \subseteq_{o,2}S$ , while $S \subseteq_{o,\infty}T$ . So in general, the questions with $S,T$ flipped are not logically related; they are different questions.

Now, back to $A(a,d) \subseteq_{o,\infty}P$ . Specifically, say that we know that there exist infinitely many $(a,d)$ such that $A(a,d) \subseteq_{o,\infty}P$ . This means at least that some $(a,d)$ exists. Thus, there exist $a,d,l$ such that $a + ld + nd$ is prime for $n \geq 0$ . We can redefine symbols and equivalently say that there exist $a,d$ such that $a + nd$ is prime for $n \geq 0$ . This implies in particular infinitely many prime tuples of the form $(p,p + d)$ (just looking at consecutive terms in $a + nd$ .) Thus, this implies that there exists $d$ such that there are infinitely many prime tuples $(p,p + d)$ . (Presumably, $d > 0$ .) So this would actually be a substantial result, and I think this implication is one that is known but not obviously. (However, I tried a cursory Google search and couldn’t find that result; that there exist infinitely many primes $p$ such that $p + 2$ , $p + 4$ , or $p + 6$ is prime — or a result similar to that — is not the same, unless I’m missing a provable equivalence.)

Actually, we can disprove this, for any $(a,d)$ ; in other words, for no $(a,d)$ does $A(a,d) \subseteq_{o,\infty}P$ . To show this, assume that we had $(a,d)$ such that $A(a,d) \subseteq_{o,\infty}P$ , so that there exists $l$ such that $P$ contains all the numbers $a + ld + nd$ , $n \geq 0$ . This would mean that for sufficiently large primes, there could not exist a prime gap larger than $d$ . But this is false, since for any $N$ , there are at least $(N - 2) + 1 = N - 1$ composite numbers in the sequence $N! + 2,\ldots,N! + N$ . Simply choose $N$ such that $N - 1 > d$ , and we have a contradiction. (Thanks to my friend Alex for showing me this cool proof that prime gaps can get arbitrarily large.)

In this sense, Dirichlet’s theorem and the Green-Tao theorem are “sharp,” resisting generalization by this avenue.

So in terms of just our inclusion chain above (when introducing the $\subseteq_{o,k}$ notation), and quantifying over $(a,d)$ as “exist infinitely many,” the sharpest possible results are known. By messing with quantifiers, is there a way to encompass outstanding conjectures like the Twin Primes Conjecture under one of the inclusion chain statements?

First, as we just proved, it is false that there exists some $(a,d)$ such that $A(a,d) \subseteq_{o,\infty}P$ . So barring switching $P$ and $A(a,d)$ (which we can consider next), we need to consider weaker statements. The two next weakest statements are known for infinitely many $(a,d)$ . What is a stronger quantifier here?

We know that $\left| A(a,d) \cap P \right| = \infty$ and $\forall k\left( A(a,d) \subseteq_{o,k}P \right)$ are both false in general for all $(a,d)$ . But we know that the former is true in general for all $(a,d)$ with $\gcd(a,d) = 1$ . What about the latter? In other words, what if we say that: for all $k$ and for all $(a,d)$ with $\gcd(a,d) = 1$ , we have $A(a,d) \subseteq_{o,k}P$ ? I still think this fails under a previous disproof, with $d$ odd; indeed, we can easily choose $(a,d)$ relatively prime with say $d = 7$ , so this fails. What about just the latter statement but with $d$ even (avoiding this trivial disproof)? In other words, what if we say that: for all $k$ , and for all even $d$ , there exists $a$ with $A(a,d) \subseteq_{o,k}P$ ? Does this encompass a conjecture like Twin Primes or Prime Tuples?

Well, first, we can note that “there exists $a$ ” is equivalent to “there exist infinitely many $a$ ”: for any suitable $(k,d)$ , say we pick some satisfying $a$ , so that there exists $l$ such that $a + ld + id \in P$ for $i \in \lbrack 0,k)$ . Then for any $j$ we can define $a^{'} = a + jd$ and $l^{'} = l - j$ , so that $a + ld = a^{'} + l^{'}d$ and $a^{'}$ also satisfies the statement. Thus, the statement is that: for any suitable $(k,d)$ , there exist $a,l$ such that $a + ld + id \in P$ for $i \in \lbrack 0,k)$ . And redefining symbols, this statement can be written as: for any suitable $(k,d)$ , there exists $a$ such that $a + id \in P$ for $i \in \lbrack 0,k)$ . As we have already seen, the particular case of $k = d = 2$ doesn’t imply the Twin Prime Conjecture, since we’re only asserting existence of one $a$ . But what about $d = 2$ but $k$ arbitrary? That would imply that $a,a + 2,\ldots,a + 2(k - 1)$ are all prime. In other words, for any $k$ , there exists $a$ such that $a,a + 2,a + 4,\ldots,a + 2(k - 1)$ are all prime. Does this yield the Twin Prime Conjecture?

Say that the Twin Prime Conjecture was false, so that there were finitely many twin primes, say $K$ of them. Choose $k$ with $k - 1 > K$ . The sequence above exhibits $k$ twin primes already: $(a,a + 2),(a + 2,a + 4),\ldots,\left( a + 2(k - 2),a + 2(k - 1) \right)$ . This is a contradiction. Thus, this statement would imply the Twin Prime Conjecture.

Is it obviously false? Does this statement fall prey to the arbitrary-large prime gap that we discussed earlier? Not necessarily in and of itself, since we can just pick $a$ such that these numbers are not within a particular gap of the form $N! + 2,\ldots,N! + N$ . It would take more work to figure this out.

Actually, this is clearly wrong. Regardless of $a$ , the sequence $(a,a + 2,a + 4)$ cannot possibly be all prime since they’re all different residues mod 3 (it’s not an admissible tuple.) So this couldn’t possibly be true for all $k$ .

We can use this logic to quickly exclude lots of $d$ . Specifically, let $d$ be arbitrary, and let $S(d)$ be the statement that “for all $k$ , there exists $a$ such that $A(a,d) \subseteq_{o,k}P$ .” The Green-Tao theorem shows that there exists $d$ such that $S(d)$ . But we’ve just seen that $S(2)$ is false. To see for what $d$ we have that $S(d)$ is false by similar logic, we need to see for what $d$ the sequences $(d,2d,\ldots,kd)$ are not all admissible. If there exists $k$ such that $(d,2d,\ldots,kd)$ is not admissible, then $S(d)$ is false. Can we conjecture that for all other $d$ that the generalization of the Green-Tao theorem is true?

Then, given $d$ , which cases of the prime tuples conjecture does $S(d)$ imply? It clearly implies that there are infinitely many tuples of form $(p,p + d)$ , by an argument similar to $S(2)$ implying the Twin Prime conjecture. (Thus, this actually means that the Green-Tao theorem implies that there exists $d$ such that there are infinitely many tuples of the form $(p,p + d)$ .) In fact, by similar logic, it seems that $S(d)$ implies that for any $m_{1} < m_{2} < \ldots < m_{t}$ such that $\left( m_{1}d,m_{2}d,\ldots,m_{t}d \right)$ is admissible, there are infinitely many prime tuples of form $\left( p + m_{1}d,p + m_{2}d,\ldots,p + m_{t}d \right)$ . Furthermore, if $d$ satisfies the necessary condition we’ve just outlined, it would be reasonable if we found that for any $m_{1} < \ldots < m_{t}$ that $\left( m_{1}d,\ldots,m_{t}d \right)$ is admissible.

It remains to study this more.

Share and like (need WordPress account to like):

Leave a comment Cancel reply