4
$\begingroup$

EDIT- result. westzynthius(1931) showed that we can create a $p_x$ denizen longer than $p_x \times log(log(log(p_x)))$... Meaning for large enough prime numbers, the maximum denizen is much larger than $2p_x, 3p_x$ etc.

Definition - Denizen

A sequence $\lbrace a_k \rbrace$ is a denizen if all of it's members are prime numbers, i.e $a_0, a_1, ... a_n \in \mathbb{P} $; and it satisfies the following condition; if "$a_{x_1} =y_1 $", "$a_{x_2} =y_2$", "$x_1 \pm m_1y_1 \neq x_2 \pm m_2 y_2 $ when $y_2<y_1 $" and "$m_3$ isn't divisible by $y_1$"; then "$a_{x_1 \pm m_1y_1}=y_1$" and $"a_{x_1 \pm m_3} \neq y_1$" (where $m \in\mathbb{N}$ where $y \in\mathbb{P}$ and where $x \in\mathbb{Z}$).

Let a denizen consisting of prime numbers up to and including $p_\alpha$ be denoted $\lbrace a_k \rbrace ^{p_\alpha} $. For example; a denizens that can be denoted as $\lbrace a_k \rbrace^7 $ is {2,7,2,3,2,5,2}.

Question

What is the maximum length $\lbrace a_k \rbrace ^{p_\alpha} $ can take?

Attempt

In order to find the maximum length a denizen $\lbrace a_k \rbrace ^{p_\alpha} $ can take I considered denizens of two different types.

I first considered a denizen $\lbrace a_k \rbrace ^{p_\alpha} $ of a type which corresponds to the sequence of natural numbers $ \lbrace 2,3,4,...,p_{\alpha +1} -1 \rbrace $. The corresponding denizen is $\lbrace 2,3,2,...,2 \rbrace $. This type of denizen had been created such that $a_i=d_i|i$, where $d_i$ is some divisor of $i$, implies $a_i \in $$\lbrace a_k \rbrace$. The consequence of this property is that this type of denizen can be considered a sequence of the lowest prime divisors of the natural numbers from $2$ to $p_{\alpha +1} -1$ respectively. For example, of this type; $\lbrace a_k \rbrace ^{11} = \lbrace 2,3,2,5,2,7,2,3,2,11,2 \rbrace $ and corresponds to $\lbrace 2,3,4,5,6,7,8,9,10,11,12 \rbrace$.

A denizen $\lbrace a_k \rbrace ^{p_\alpha} $ of this type which has a length of $ p_{\alpha +1} -2 $.

However I found a larger type of denizen corresponding to the sequence of integers $\lbrace -(p_{\alpha -1} -1), ..., -4,-3,-2,-1,0,1,2,3,4, ..., p_{\alpha -1} -1 \rbrace $. The corresponding denizen is $\lbrace 2, ..., 2,3,2,p_\alpha,2,p_{\alpha -1},2,3,2, ..., 2 \rbrace $. This type of denizen can also be considered a sequence of lowest prime factors of the integer sequence above, however it also requires the replacement of $-1$ and $1$ with the two primes $p_{\alpha}$ and $p_{\alpha -1}$ respectively and involves replacing $0$ with $2$. For example, of this type $\lbrace a_k \rbrace ^{11} = \lbrace 2,5,2,3,2,7,2,11,2,3,2,5,2 \rbrace $ and corresponds to $\lbrace -6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6 \rbrace$.

This type of denizen has a length of $ 2p_{\alpha -1} -1 $ and also has an apparent symmetry as defined below. this type of denizen has a length greater or equal to the length of the previous type because of the identity $2p_{x-2} \geq p_{x}-1$ proved here.

So my next question is; is the second type of denizen the largest lengthed $\lbrace a_k \rbrace ^{p_\alpha} $ denizen possible? How could you prove it was?

I have tried to prove this, using the concept of symmetry. I defined the symmetric depth as the largest prime number $p_N$ such that $a_{x+ p_N}=a_{x- p_N} = p_N$ and $a_{x+ p_{i}}=a_{x- p_{i}} =p_i$ for all prime numbers $p_i$ less than $p_N$, centred on some $a_x\in \lbrace a_k \rbrace$. I let $\lbrace a_k \rbrace ^{p_\alpha} _ {p_N} $ be a denizen consisting prime numbers upto and including $p_\alpha$ with symmetric depth $p_N$, and hoped to prove that the length of a denizen $\lbrace a_k \rbrace ^{p_\alpha} _ {p_N} $ is always greater than or equal to the length of a denizen $\lbrace a_k \rbrace ^{p_\alpha} _ {p_{N-1}} $. However I found a counter example to this, due to the fact that the gaps between large prime numbers tend to be greater than the gaps between smaller prime numbers.

However I have yet to produce a denizen $\lbrace a_k \rbrace ^{p_\alpha} $ greater in length than $\lbrace a_k \rbrace ^{p_\alpha} _ {p_{\alpha -2}} $.

So any ideas to further this?

Further Questions

Definition - Apparent width

In a denizen $\lbrace a_k \rbrace$, if $p_A$ is the largest prime number such that $a_{i+ mp_A}$ and $a_{i- mp_A}$ are prime number greater than or equal to $p_A$ then $a_i$ has an apparent width of $p_A$. Furthermore; if the apparent width of $a_i$ is larger then all other apparent widths of members in $\lbrace a_k \rbrace$ then the apparent width of $\lbrace a_k \rbrace$ is $p_A$.

Can there be a denizen $\lbrace a_k \rbrace ^{p_x}$ that has an apparent width strictly less than some $p_\beta$, but that has a length that is greater than another denizen $\lbrace a_k \rbrace^{p_x}$ with apparent width of $p_\beta$?

Furthermore, are all denizen $\lbrace a_k \rbrace ^{p_x}$ with an apparent width of $p_\beta$ less than or equal to in length to the smallest denizen $\lbrace a_k \rbrace ^{p_x}_{p_\beta}$?

$\endgroup$
  • 2
    $\begingroup$ If $a_x=y$ implies $a_{x\pm my}=y$, then $a_x=a_{x\pm my}$, so what is the meaning of $\forall x a_x\le a_{x\pm my}$? What are the dots in $2,3,2,\dots,2$? In what way does $2,3,2\dots,2$ correspond to $2,3,4,\dots,p_{a+1}-1$? The whole thing is incomprehensible. I'm sure you know what you mean, but please try explaining it to a friend, and don't stop until the friend understands it, and then edit into your question everything you had to tell your friend to make her understand it. $\endgroup$ – Gerry Myerson Aug 23 '15 at 6:52
  • 2
    $\begingroup$ It is not clear what a denizen sequence is. It seems that any constant sequence of a prime is denizen... $\endgroup$ – Joel Moreira Aug 23 '15 at 17:39
  • 3
    $\begingroup$ No. There is still no explanation in the body of the question as to what the dots in $2,3,2,\dots,2$ mean. There is still no explanation in the body of the question as to what it means for $2,3,2,\dots,2$ to correspond to $2,3,4,\dots,p_{a+1}-1$. $a_i=d\mid i$ makes no sense. Can you write out one denizen, say, $\{\,a_k\,\}^5$, in complete detail, with no dots? By the way, if you want to be certain that I see a comment addressed to me, you have to put in @Gerry. $\endgroup$ – Gerry Myerson Aug 24 '15 at 12:55
  • 3
    $\begingroup$ @BradGraham Gerry isn't being overly critical. Your definition is missing about five or six quantifiers and you don't provide enough words to fill in the blanks. Sometimes when you build up a concept over a period of time, there are details that are so "obviously necessary" that you don't realize that you haven't stated them, but are essential to others' understanding. Please do take a step back and make an effort to explain what you're doing. $\endgroup$ – Erick Wong Aug 24 '15 at 15:44
  • 3
    $\begingroup$ @BradGraham I appreciate you've made an effort, but I don't think you have given much thought to distilling the definition to its essence. For starters, I have no idea what $x_1 \pm m_1 y_1 \ne x_2 \pm m_2 y_2 : y_2 < y_1$ is supposed to mean. It's a mash of symbols with no quantifiers: there are two (or more, since $m_1$ and $m_2$ aren't quantified) numbers on each side of the $\ne$ (are all pairs not equal? just the corresponding $+$ and $-$ cases? who can tell without any words?). Why is there a $:$ before $y_2 < y_1$? $\endgroup$ – Erick Wong Aug 24 '15 at 15:58
3
+100
$\begingroup$

Your definition of denizen is a very baroque, confused way to describe an extremely simple concept: you're just asking for the longest interval that can be covered with arithmetic progressions, one for each prime up to $p$. When the same number is covered by multiple progressions, you went to great pains to force the denizen to record only the least modulus. But that distinction is completely irrelevant to the problem of optimizing the interval length.

This problem has been worked on since the 1930s by Westzynthius, and was made famous by Erdős and later Rankin. See this MO question which asks essentially the same question, but gives an excellent exposition of the methods.

Rankin used this method to show that the largest gap between primes up to $x$ is at least $$\Omega\bigg(\frac{\log x \log \log x \log \log \log \log x}{(\log\log\log x)^2}\bigg).$$

This stood for decades as the strongest growth rate for large prime gaps, until last year when several of the most distinguished researchers in the field sharpened the $\Omega$ to an $\omega$. So it is a very well-studied problem.

OEIS has an entry for the maximum denizen length of type $\{a_k\}^{p_a}$ for several small values of $a$: http://oeis.org/A058989. This answers your question about the "second type of denizen" being the longest possible: it becomes false starting at $p_a = 23$, which has a denizen of length $39 > 2\cdot19-1$.

$\endgroup$
  • $\begingroup$ It looks like the result you have quoted is very baroque! With regards to the question in the post "If you take arithmetic progressions whose differences are the primes up to $z$, must there be an integer smaller than $O(z^2)$ which is not covered by any arithmetic progression?". Actually this is essentially a different question to what I am asking. I'm not looking at whether there are gaps up to $p_z^2$. I'm asking whether the first gap can occur after $2p_{z-2}$. $\endgroup$ – Brad Graham Aug 26 '15 at 15:59
  • 2
    $\begingroup$ @BradGraham Don't focus so much on the result (it may look complex but that's only because the amount that can be accomplished is so small that a certain level of precision is needed just to distinguish the asymptotic from the trivial bound and earlier results). From what I can tell, the covering question exactly matches your definition of longest denizen. If you can see a specific way it doesn't match, then you need to provide a clear definition (for once). $\endgroup$ – Erick Wong Aug 26 '15 at 17:33
0
$\begingroup$

This is not complete answer, but this answer is illustrative of one way we could try to attempt to answer the first question posted.

Consider $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$.

$\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$ has possible two forms: $\lbrace 2, ..., 2,3,2,p_x,2,p_{x-1},2,3,2,...,2 \rbrace$ or $\lbrace 2, ..., 2,3,2,p_{x-1},2,p_{x},2,3,2,...,2 \rbrace$. If we interchange any other members except $p_{x-1}$ and $p_x$, then the resulting denizen will have a symmetric depth less than $p_{x-2}$. Therefore the longest denizen of the form $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$ has a length of $2p_{x-1}$ because of its forms do.

Suppose there exists a denizen $\lbrace a_k \rbrace ^{p_x}$ longer than $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$. It must have a symmetric depth strictly less than $p_{x-2}$. Secondly all denizens longer than $11$ have a symmetric depth of at least $3$. This is because one of the first four terms of the sequence must be $3$, and also the term six places to the right of this must also be $3$.

So let the length of $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}} \geq 11$. Therefore, the longest denizen must have the form $\lbrace a_k \rbrace ^{p_x} _{p_{y}}$ where $3 \leq p_y < p_{x-2}$.

The length of $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$ is equal to the length of $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}} + 2\times (p_{x-1}-p_{y+1})$. This is because $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$ has a length of $2p_{y+1}$. So the statment is equivalent to saying that $2p_{x-1} = 2p_{y+1} +2\times (p_{x-1} -p_{y+1})=2p_{y+1} +2p_{x-1} -2p_{y+1}=2p_{x-1}$. Similarly the length of $\lbrace a_k \rbrace ^{p_x} _{p_{y}} $ equals the length of $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$, as this is the the symmetry, plus some $R$, which is unknown.

Therefore if $\lbrace a_k \rbrace ^{p_x} _{p_{y}} > \lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$ then $R > 2\times (p_{x-1}-p_{y+1})$.

To intepret the term $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}} +2\times (p_{x-1}-p_{y+1})$ we can note that $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$ is a sequence where if we have an odd prime number larger than $p_{y}$, we can place it at one of the two ends of the sequence $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$ and consequently we can also place $2$ as a member before or after it, because the longest denizen will trivially start with a $2$ and end with a $2$. So we can intepret $2\times (p_{x-1}-p_{y+1})$ as saying; 'Add $p_{x-1}-p_{y+1}$ odd prime numbers onto $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$, and consequently add $p_{x-1}-p_{y+1}$ $2$'s. '

From this observation, we know that $R$ must be also even, therefore let $R=2R'$, and this implies that we can add $R'$ odd prime numbers onto $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$, where $R'> p_{x-1}-p_{y+1}$.

So consider adding $R'$ odd primes onto $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$. Each odd prime number must be less than or equal to $p_x$, because we are determining the maximum length of a $\lbrace a_k \rbrace ^{p_x}$ denizen. This gives us $x-1$ odd primes that we can use to extend $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$, although $y$ of those odd primes have had their positions predetermined by the symmetric denizen $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$, therefore we have $x-1-y$ odd primes that we can freely position, in order to maximise the length of $\lbrace a_k \rbrace ^{p_x} _{p_{y}}$.

The next point to make is on the position that the $R'$ odd primes take in respect to $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$. Consider the situation where all $R'$ odd prime numbers attach to the same side of $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$. We may be able to take off an odd prime number from this side and attach it to the other side of $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$. We can continue doing this until all odd primes are attached to the other side. However, when over half the odd primes have been attached to the other side of $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$, note that the structure of this denizen has already already been accounted for when over half the odd primes hadn't been moved. It is unknown whether $R'$ is odd or even, so let $R'=2R''$ plus a one if $R'$ is odd. Therefore there are $R''$ possibilities for the placement of the $R'$ spaces in respect to $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$.

We now know that we have less then or equal to $R' \times R'' \times (x-1-y)$ arrangements of the odd primes greater than $p_y$ to try, in order to maximize the length of $\lbrace a_k \rbrace ^{p_x} _{p_{y}}$. Note we have said less than, because there is at least one more complexity to incorporate into the situation. Of the $R'$ spaces we are want to fill with one of the $(x-y-1)$ prime numbers, some of these spaces have already been predetermined to be a prime number less than or equal to $p_y$ by the symmetric denizen $\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$. The next question is, of the $R'$ spaces, how many free spaces are there for the free prime numbers?

I don't have time to think through the next part of this attempt, but continuing this line of thinking, we may be able to reach the number of possibilities for the structure of $\lbrace a_k \rbrace ^{p_x} _{p_{y}}$. We can lower this by removing impossible structures such as those which produce a larger symmetry. If we can show that one of the remaining possibilities implies $R' >p_{x-1} -p_{y+1}$ then we know that $\lbrace a_k \rbrace ^{p_x} _{p_{x-2}}$ is not the largest $\lbrace a_k \rbrace ^{p_x}$ denizen. If show that $R' \leq p_{x-1} -p_{y+1}$ for all of the possibilities, then by exhaustion we reach a contradiction. (Remember $R=2R'=\lbrace a_k \rbrace ^{p_x} _{p_{y}} -\lbrace a_k \rbrace ^{p_{y+2}} _{p_{y}}$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.