0

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?

Community
  • 1
Brad Graham
  • 161
  • Question also posted, without notice to either site, to m.se: http://math.stackexchange.com/questions/1404429/the-longest-sequence-of-numbers-with-a-certain-divisibility-property – Gerry Myerson Aug 24 '15 at 06:45
  • Distantly related: some years ago, my co-authors and I defined the concept of an IRDCS of length $n$. The smallest example, of length 11, is $6,9,3,4,5,3,6,4,3,5,9$. Note that for each $m$ appearing in the list, $m$ appears at every $m$th position, and only at every $m$th position; also, every $m$ that appears appears at least twice. – Gerry Myerson Aug 24 '15 at 23:19
  • I'm curious about what the purpose for creating the concept of an IRDCS was and why the numbers $6,9,3,4,5$ were chosen? Essentially a placement condition is one of the requirements of a denizen; a prime number will appear in the $m$th position if it is the lowest prime factor of $m$. I note that an IRDCS allows two consecutive terms to be odd so it doesn't look like it was created to represent a section of the natural number line. Denizens were created to represent the sequence of composite numbers between two consecutive primes. – Brad Graham Aug 24 '15 at 23:46
  • 1
    There's a theorem that says you can't partition the integers into finitely many arithmetic progressions with different common differences. An IRDCS is a partition of a finite segment of the integers into arithmetic progressions with different common differences, so it shows you can't weaken the theorem hypotheses too much. The numbers were chosen because they work: there is no IRDCS shorter than length 11, and the only one of length 11 is the one I gave, and its reverse. Try it! – Gerry Myerson Aug 25 '15 at 02:41
  • I am still having trouble understanding your definition of denizen. To me it looks like you are looking at sequences of the form L(a+1),L(a+2),...,L(a+m) where a and m are positive integers and L() is the least prime factor. If so, there are better ways of characterising denizens, and there is literature and some computation involving longer denizens. Search on this forum for "Westzynthius" for some detail. Gerhard "Good To Be Back Home" Paseman, 2015.08.29 – Gerhard Paseman Aug 29 '15 at 18:33
  • Oh, and I suspect the maximum length is bounded from above (for all but finitely many $a$) by $p_a(\log p_a)^2$, and more likely by something not much larger than $p_a\log p_a$. Gerhard "Speaking From Somewhat Limited Experience" Paseman, 2015.08.29 – Gerhard Paseman Aug 29 '15 at 18:42
  • @GerhardPaseman thank you. Yeah that's pretty much it, and I'm trying to maximise the length of the denizen consisting of only prime numbers up to some $p_x$. The definition tries to capture the axioms that restrict the sequence you mentioned, so that we don't need to know "a" "a+1" etc. I also came across Erdos' attempts at a similar problem using arithmetic sequences, and i realised that perhaps this in not the best approach to finding a maximum distance between two prime numbers. – Brad Graham Aug 29 '15 at 18:42
  • I have yet to find a denizen consisting of prime numbers upto $p_x$ that has a length greater than $2p_{x-1}, and i suspect that is an upper bound. – Brad Graham Aug 29 '15 at 18:44
  • Others have thought that was the upper bound, and were wrong. It may not be the best way, but it is (according to Terry Tao and others in their December ArXiv preprint) the way used by most researchers on lower bounds of prime gaps. If you edit the question to reflect the viewpoint I suggested above, it might be closed as a duplicate on this forum. If you edit it to show clearly a key idea or insight using your definition, I am willing to consider it. Gerhard "Always Looking For New Ideas" Paseman, 2015.08.29 – Gerhard Paseman Aug 29 '15 at 18:45
  • Well the key insight is that all prime numbers less than some $p_{x}^2$ are those numbers not divisible by a prime less than $p_{x}$ except for those primes themselves. In effect we are creating maximum gaps relative to squared primes by creating sieves corresponding to prime numbers less the prime squared. – Brad Graham Aug 29 '15 at 18:49
  • @GerhardPaseman i would love to see a counter example. – Brad Graham Aug 29 '15 at 18:52
  • There is likely an example computed already (I know Westzynthius has one in his paper for primes up to 23). The best link I have right now is http://mathoverflow.net/questions/49400/question-in-prime-numbers . Gerhard "Yes, It's Been Done Before" Paseman, 2015.08.29 – Gerhard Paseman Aug 29 '15 at 18:56
  • Sorry but thats not a counter example! – Brad Graham Aug 29 '15 at 18:59
  • 1
    23252a232b2_23272_232_25232a2723252b232 . Length 39. a and b represent the primes 11 and 13. Fill in the three blanks with 17, 19, and 23. Use Chinese Remainder Theorem to calculate the numbers corresponding to the digits, or lookup Westzynthius. Gerhard "And There Are Larger Examples" Paseman, 2015.08.30 – Gerhard Paseman Aug 31 '15 at 02:49
  • Excellent so there are larger denizens! – Brad Graham Aug 31 '15 at 02:56
  • @GerhardPaseman Now to try and explain why there exists a denizen$\lbrace a_k \rbrace^{23}_5$ larger than $\lbrace a_k \rbrace^{23}_17$ i'll look up Westzynthius thank you. – Brad Graham Aug 31 '15 at 03:00
  • I think you will find nonsymmetric patterns will abound with large values of x. You might consider looking at recent papers on large prime gaps. They are implicitly constructing denizens using a log's worth of small primes and interesting sprinklings of large primes, starting with a base of medium primes. I think the symmetric depth for these will be pretty small, and I don't even understand the definition of symmetric depth. Gerhard "Check Out Rankin And Pomerance" Paseman, 2015.09.03 – Gerhard Paseman Sep 03 '15 at 19:05
  • @Gerhard Consider the denizen $2,5,2,3,2,7,0,11,2,3,2,5,2$. I have used $0$ to represent its centre (although it should be a 2). If in this sequence $0$ has position $k$, we can see a $2$ at position $k \pm 2$, a $3$ at position $k \pm 3$ and a $5$ at position $k \pm 5$. So we can $0$ has a symmetric depth of $5$. Now, as the symmetric depth of all other members in this sequence is less than $5$, then this denizen has a symmetric depth of $5$. I initially thought the longest denizen consisting of prime numbers upto $p_x$ was the $p_x$ denizen with symmetric depth of $x-2$. – Brad Graham Sep 03 '15 at 19:18
  • Which is as I suspected, a pattern of least prime factors of integers n with central number a multiple of a primorial. While some of the large prime gaps are near multiples of large primorials, many do not have such multiples near the center. I show my bias when I say it makes more sense to study the distribution of totatives to a primorial, and see where those large gaps appear. Gerhard "Sensing A Philosophical Clash Here" Paseman, 2015.09.03 – Gerhard Paseman Sep 03 '15 at 19:26
  • @Gerhard Its strange because for the smallest prime numbers (upto 23), the denizen centred at a primorial is the largest... So what happens after 23? What the best explanation in mathematical terms? And yeah it makes sense to look at the totatives, but describing their distribution naturally is difficult when we cant even say how far apart they are at most! – Brad Graham Sep 03 '15 at 19:37
  • I've considered splitting, the interval of integers $I=[0, p_x # !)$, into intervals with $p_y \in \mathbb{P}$ length and that are complete residues of $p_y$, where $p_y \leq p_x$. In each of these smaller intervals; $(p_y -1)/p_y$ numbers are not divisble by $p_y$. From this, its easy to show that atleast $1/p_x$ of the numbers in $I$ are totatives. From this, if we half the interval I, we can say there are half as many numbers not divisible by any prime upto $p_x$ except $2$. There are just under or over a half the amount of even numbers in I. So following this approach, can we find a small – Brad Graham Sep 03 '15 at 19:55
  • Smallest interval that contains a totative of a primorial? Thats my next approach in the future. – Brad Graham Sep 03 '15 at 19:56
  • @Gerhard do you know of any $p_x$-denizen longer than $4p_x$? – Brad Graham Sep 06 '15 at 03:07
  • To name, no. However, you can use Westzynthius's construction to build one. It will require lots of primes. Current calculations suggest you will need x > 50. Gerhard "Check Out Thomas Hagedorn's Paper" Paseman, 2015.09.05 – Gerhard Paseman Sep 06 '15 at 04:52
  • @Gerhard you might be interested in this open question http://mathoverflow.net/questions/217756/the-number-of-totatives-to-the-nth-primorial-in-an-interval-shorter-than-the-nt – Brad Graham Sep 08 '15 at 13:57

0 Answers0