Do the primes contain an infinite almost arithmetic progression? The Next CEO of Stack OverflowConstructing arithmetic progressionsProve that $sqrt[3]p$, $sqrt[3]q$ and $sqrt[3]r$ cannot be in the same arithmetic progressionA question on Primes in Arithmetic ProgressionWhich progressions and sequences are guaranteed to contain infinitely many primes?Primes and arithmetic progressionsWeak form of Dirichlet's theorem.Prime Factors of the Composit Terms of Arithmetic ProgressionsA question about arithmetic progressions and prime numbersArithmetic Progressions of PrimesA Question about the Green-Tao Theorem on Arithmetic Progressions in Primes
What do "high sea" and "carry" mean in this sentence?
How can I get through very long and very dry, but also very useful technical documents when learning a new tool?
Why didn't Khan get resurrected in the Genesis Explosion?
How should I support this large drywall patch?
Help understanding this unsettling image of Titan, Epimetheus, and Saturn's rings?
Keeping you safe
Inappropriate reference requests from Journal reviewers
Why do remote companies require working in the US?
Opposite of a diet
Complex fractions
How to draw dotted circle in Inkscape?
What happened in Rome, when the western empire "fell"?
WOW air has ceased operation, can I get my tickets refunded?
My Curious Music Box
A "random" question: usage of "random" as adjective in Spanish
What can we do to stop prior company from asking us questions?
Is it professional to write unrelated content in an almost-emtpy email?
How to get regions to plot as graphics
Is there a difference between "Fahrstuhl" and "Aufzug"
How to make a variable always equal to the result of some calculations?
What benefits would be gained by using human laborers instead of drones in deep sea mining?
Why do professional authors make "consistency" mistakes? And how to avoid them?
Does it take more energy to get to Venus or to Mars?
How to count occurrences of text in a file?
Do the primes contain an infinite almost arithmetic progression?
The Next CEO of Stack OverflowConstructing arithmetic progressionsProve that $sqrt[3]p$, $sqrt[3]q$ and $sqrt[3]r$ cannot be in the same arithmetic progressionA question on Primes in Arithmetic ProgressionWhich progressions and sequences are guaranteed to contain infinitely many primes?Primes and arithmetic progressionsWeak form of Dirichlet's theorem.Prime Factors of the Composit Terms of Arithmetic ProgressionsA question about arithmetic progressions and prime numbersArithmetic Progressions of PrimesA Question about the Green-Tao Theorem on Arithmetic Progressions in Primes
$begingroup$
The primes contain finite arithmetic progressions of arbitrary length, but not an infinite arithmetic progression. Say we define an almost arithmetic progression to be a sequence $a_k$, $k geq 0$, such that there exist $a,d$ such that $a_k = a+kd + O(sqrtk)$. Do the primes contain an infinite almost arithmetic progression?
(The definition is ad hoc and just made up out of curiosity. I wrote the “error term” $O(sqrtk)$ in analogy to the expectation of a random walk. An obvious generalization of the question is to replace this with some other “small” error term like $O(ln k)$ or whatever.)
number-theory prime-numbers
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
$endgroup$
add a comment |
$begingroup$
The primes contain finite arithmetic progressions of arbitrary length, but not an infinite arithmetic progression. Say we define an almost arithmetic progression to be a sequence $a_k$, $k geq 0$, such that there exist $a,d$ such that $a_k = a+kd + O(sqrtk)$. Do the primes contain an infinite almost arithmetic progression?
(The definition is ad hoc and just made up out of curiosity. I wrote the “error term” $O(sqrtk)$ in analogy to the expectation of a random walk. An obvious generalization of the question is to replace this with some other “small” error term like $O(ln k)$ or whatever.)
number-theory prime-numbers
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
$endgroup$
1
$begingroup$
Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense.
$endgroup$
– Carl Mummert
Mar 22 at 16:49
$begingroup$
@CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight.
$endgroup$
– Zach Teitler
Mar 23 at 6:50
add a comment |
$begingroup$
The primes contain finite arithmetic progressions of arbitrary length, but not an infinite arithmetic progression. Say we define an almost arithmetic progression to be a sequence $a_k$, $k geq 0$, such that there exist $a,d$ such that $a_k = a+kd + O(sqrtk)$. Do the primes contain an infinite almost arithmetic progression?
(The definition is ad hoc and just made up out of curiosity. I wrote the “error term” $O(sqrtk)$ in analogy to the expectation of a random walk. An obvious generalization of the question is to replace this with some other “small” error term like $O(ln k)$ or whatever.)
number-theory prime-numbers
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
$endgroup$
The primes contain finite arithmetic progressions of arbitrary length, but not an infinite arithmetic progression. Say we define an almost arithmetic progression to be a sequence $a_k$, $k geq 0$, such that there exist $a,d$ such that $a_k = a+kd + O(sqrtk)$. Do the primes contain an infinite almost arithmetic progression?
(The definition is ad hoc and just made up out of curiosity. I wrote the “error term” $O(sqrtk)$ in analogy to the expectation of a random walk. An obvious generalization of the question is to replace this with some other “small” error term like $O(ln k)$ or whatever.)
number-theory prime-numbers
number-theory prime-numbers
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
asked Mar 22 at 16:34
Zach TeitlerZach Teitler
2,281419
2,281419
1
$begingroup$
Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense.
$endgroup$
– Carl Mummert
Mar 22 at 16:49
$begingroup$
@CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight.
$endgroup$
– Zach Teitler
Mar 23 at 6:50
add a comment |
1
$begingroup$
Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense.
$endgroup$
– Carl Mummert
Mar 22 at 16:49
$begingroup$
@CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight.
$endgroup$
– Zach Teitler
Mar 23 at 6:50
1
1
$begingroup$
Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense.
$endgroup$
– Carl Mummert
Mar 22 at 16:49
$begingroup$
Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense.
$endgroup$
– Carl Mummert
Mar 22 at 16:49
$begingroup$
@CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight.
$endgroup$
– Zach Teitler
Mar 23 at 6:50
$begingroup$
@CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight.
$endgroup$
– Zach Teitler
Mar 23 at 6:50
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Note: I allow for $a_k$ to repeat. If you wish to keep them distinct, the answer by N. S. gives a negative answer.
The answer is: we don't know, but probably. Indeed, your question is equivalent to the question of whether the prime gaps satisfy $p_n+1-p_n=O(sqrtp_n)$, as I explain below. This bound is widely believed to hold - indeed, the running conjecture (Cramér's conjecture) is that we even have $p_n+1-p_n=O((log p_n)^2)$, but we are quite far from proving it. The best unconditional bound we have is $p_n+1-p_n=O(p_n^0.525)$, and assuming the Riemann hypothesis we can push this to $O(p_n^1/2+varepsilon)$, but not to $O(sqrtp_n)$. (see Wikipedia)
To see the equivalence, take some infinite almost arithmetic progression. Suppose the $O(sqrtk)$ term is bounded by $Msqrtk$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+Msqrtk$. Then $p_n+1leq a_kleq a+dk+Msqrtkleq d+p_n+Msqrtk+Msqrtk=p_n+O(sqrtk)=p_n+O(sqrtp_n)$.
Conversely, suppose gaps between primes are $O(sqrtp_n)$. Take $a=0,d=1$ and $a_k$ the smallest prime greater than $k$. The assumption trivially implies $a_k=k+O(sqrtk)$.
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
$endgroup$
1
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
add a comment |
$begingroup$
The answer is NO.
Note that any set $S$ containing an infinite almost arithmetic progression satisfies
$$
underlinemboxdens(S):= liminf_n frac(mboxcard( S cap [0,n]))n geq frac1d$$
But the primes have density $0$.
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
add a comment |
$begingroup$
The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence.
On the other hand, you will be able to find a very long sequence of primes $a_k$ where
$-10000cdot k^1/2 ≤ a_k - (3 + 10000k) ≤ 10000 cdot k^1/2$.
All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^10000$ where the densities of primes goes too low.
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3158369%2fdo-the-primes-contain-an-infinite-almost-arithmetic-progression%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Note: I allow for $a_k$ to repeat. If you wish to keep them distinct, the answer by N. S. gives a negative answer.
The answer is: we don't know, but probably. Indeed, your question is equivalent to the question of whether the prime gaps satisfy $p_n+1-p_n=O(sqrtp_n)$, as I explain below. This bound is widely believed to hold - indeed, the running conjecture (Cramér's conjecture) is that we even have $p_n+1-p_n=O((log p_n)^2)$, but we are quite far from proving it. The best unconditional bound we have is $p_n+1-p_n=O(p_n^0.525)$, and assuming the Riemann hypothesis we can push this to $O(p_n^1/2+varepsilon)$, but not to $O(sqrtp_n)$. (see Wikipedia)
To see the equivalence, take some infinite almost arithmetic progression. Suppose the $O(sqrtk)$ term is bounded by $Msqrtk$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+Msqrtk$. Then $p_n+1leq a_kleq a+dk+Msqrtkleq d+p_n+Msqrtk+Msqrtk=p_n+O(sqrtk)=p_n+O(sqrtp_n)$.
Conversely, suppose gaps between primes are $O(sqrtp_n)$. Take $a=0,d=1$ and $a_k$ the smallest prime greater than $k$. The assumption trivially implies $a_k=k+O(sqrtk)$.
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
$endgroup$
1
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
add a comment |
$begingroup$
Note: I allow for $a_k$ to repeat. If you wish to keep them distinct, the answer by N. S. gives a negative answer.
The answer is: we don't know, but probably. Indeed, your question is equivalent to the question of whether the prime gaps satisfy $p_n+1-p_n=O(sqrtp_n)$, as I explain below. This bound is widely believed to hold - indeed, the running conjecture (Cramér's conjecture) is that we even have $p_n+1-p_n=O((log p_n)^2)$, but we are quite far from proving it. The best unconditional bound we have is $p_n+1-p_n=O(p_n^0.525)$, and assuming the Riemann hypothesis we can push this to $O(p_n^1/2+varepsilon)$, but not to $O(sqrtp_n)$. (see Wikipedia)
To see the equivalence, take some infinite almost arithmetic progression. Suppose the $O(sqrtk)$ term is bounded by $Msqrtk$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+Msqrtk$. Then $p_n+1leq a_kleq a+dk+Msqrtkleq d+p_n+Msqrtk+Msqrtk=p_n+O(sqrtk)=p_n+O(sqrtp_n)$.
Conversely, suppose gaps between primes are $O(sqrtp_n)$. Take $a=0,d=1$ and $a_k$ the smallest prime greater than $k$. The assumption trivially implies $a_k=k+O(sqrtk)$.
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
$endgroup$
1
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
add a comment |
$begingroup$
Note: I allow for $a_k$ to repeat. If you wish to keep them distinct, the answer by N. S. gives a negative answer.
The answer is: we don't know, but probably. Indeed, your question is equivalent to the question of whether the prime gaps satisfy $p_n+1-p_n=O(sqrtp_n)$, as I explain below. This bound is widely believed to hold - indeed, the running conjecture (Cramér's conjecture) is that we even have $p_n+1-p_n=O((log p_n)^2)$, but we are quite far from proving it. The best unconditional bound we have is $p_n+1-p_n=O(p_n^0.525)$, and assuming the Riemann hypothesis we can push this to $O(p_n^1/2+varepsilon)$, but not to $O(sqrtp_n)$. (see Wikipedia)
To see the equivalence, take some infinite almost arithmetic progression. Suppose the $O(sqrtk)$ term is bounded by $Msqrtk$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+Msqrtk$. Then $p_n+1leq a_kleq a+dk+Msqrtkleq d+p_n+Msqrtk+Msqrtk=p_n+O(sqrtk)=p_n+O(sqrtp_n)$.
Conversely, suppose gaps between primes are $O(sqrtp_n)$. Take $a=0,d=1$ and $a_k$ the smallest prime greater than $k$. The assumption trivially implies $a_k=k+O(sqrtk)$.
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
$endgroup$
Note: I allow for $a_k$ to repeat. If you wish to keep them distinct, the answer by N. S. gives a negative answer.
The answer is: we don't know, but probably. Indeed, your question is equivalent to the question of whether the prime gaps satisfy $p_n+1-p_n=O(sqrtp_n)$, as I explain below. This bound is widely believed to hold - indeed, the running conjecture (Cramér's conjecture) is that we even have $p_n+1-p_n=O((log p_n)^2)$, but we are quite far from proving it. The best unconditional bound we have is $p_n+1-p_n=O(p_n^0.525)$, and assuming the Riemann hypothesis we can push this to $O(p_n^1/2+varepsilon)$, but not to $O(sqrtp_n)$. (see Wikipedia)
To see the equivalence, take some infinite almost arithmetic progression. Suppose the $O(sqrtk)$ term is bounded by $Msqrtk$. For any prime $p_n$, let $k$ be the least such that $a+dk>p_n+Msqrtk$. Then $p_n+1leq a_kleq a+dk+Msqrtkleq d+p_n+Msqrtk+Msqrtk=p_n+O(sqrtk)=p_n+O(sqrtp_n)$.
Conversely, suppose gaps between primes are $O(sqrtp_n)$. Take $a=0,d=1$ and $a_k$ the smallest prime greater than $k$. The assumption trivially implies $a_k=k+O(sqrtk)$.
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
answered Mar 22 at 16:52
WojowuWojowu
19.2k23174
19.2k23174
1
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
add a comment |
1
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
1
1
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
$begingroup$
Thanks. So conjecturally $p_n = a + nd + O((log n)^2)$, but the "$a+nd$" part is boring, it can just be $a=0,d=1$ (and not $O(log n)$, that is too strong I take it).
$endgroup$
– Zach Teitler
Mar 22 at 17:20
add a comment |
$begingroup$
The answer is NO.
Note that any set $S$ containing an infinite almost arithmetic progression satisfies
$$
underlinemboxdens(S):= liminf_n frac(mboxcard( S cap [0,n]))n geq frac1d$$
But the primes have density $0$.
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
add a comment |
$begingroup$
The answer is NO.
Note that any set $S$ containing an infinite almost arithmetic progression satisfies
$$
underlinemboxdens(S):= liminf_n frac(mboxcard( S cap [0,n]))n geq frac1d$$
But the primes have density $0$.
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
$endgroup$
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
add a comment |
$begingroup$
The answer is NO.
Note that any set $S$ containing an infinite almost arithmetic progression satisfies
$$
underlinemboxdens(S):= liminf_n frac(mboxcard( S cap [0,n]))n geq frac1d$$
But the primes have density $0$.
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
$endgroup$
The answer is NO.
Note that any set $S$ containing an infinite almost arithmetic progression satisfies
$$
underlinemboxdens(S):= liminf_n frac(mboxcard( S cap [0,n]))n geq frac1d$$
But the primes have density $0$.
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
edited Mar 22 at 16:44
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
answered Mar 22 at 16:39
N. S.N. S.
105k7114210
105k7114210
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
add a comment |
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
I don't think the question requires $a_k$ to be distinct.
$endgroup$
– Wojowu
Mar 22 at 16:39
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
@CarlMummert $a+kd$ has gaps of size $d$. For any $k>d^2$, it is easily possible for two terms to coincide.
$endgroup$
– Wojowu
Mar 22 at 16:47
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
Thanks; I was reading it as $O(sqrtd)$. This makes the question more confusing overall, because if the resulting sequence might not be syndetic, it's not really very similar to an arithmetical progression.
$endgroup$
– Carl Mummert
Mar 22 at 16:48
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
$begingroup$
@CarlMummert True! I didn't really think it through.
$endgroup$
– Zach Teitler
Mar 22 at 17:17
add a comment |
$begingroup$
The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence.
On the other hand, you will be able to find a very long sequence of primes $a_k$ where
$-10000cdot k^1/2 ≤ a_k - (3 + 10000k) ≤ 10000 cdot k^1/2$.
All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^10000$ where the densities of primes goes too low.
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
$endgroup$
add a comment |
$begingroup$
The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence.
On the other hand, you will be able to find a very long sequence of primes $a_k$ where
$-10000cdot k^1/2 ≤ a_k - (3 + 10000k) ≤ 10000 cdot k^1/2$.
All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^10000$ where the densities of primes goes too low.
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
$endgroup$
add a comment |
$begingroup$
The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence.
On the other hand, you will be able to find a very long sequence of primes $a_k$ where
$-10000cdot k^1/2 ≤ a_k - (3 + 10000k) ≤ 10000 cdot k^1/2$.
All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^10000$ where the densities of primes goes too low.
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
$endgroup$
The number of primes ≤ N is about N / log (N). Your sequence would have about N / d primes ≤ N in that sequence alone, if N is large. Once N is large enough so that log N >> d, there are just not enough primes around for your sequence.
On the other hand, you will be able to find a very long sequence of primes $a_k$ where
$-10000cdot k^1/2 ≤ a_k - (3 + 10000k) ≤ 10000 cdot k^1/2$.
All you need is $a_0=3$, some prime $3 ≤ a_1 ≤ 20003$, some prime in the range 20003 +/- 14000, one in the range 30003 +/- 17000 etc. This will work until you get to the numbers around $e^10000$ where the densities of primes goes too low.
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
edited Mar 22 at 22:05
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
answered Mar 22 at 21:50
gnasher729gnasher729
6,1401128
6,1401128
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3158369%2fdo-the-primes-contain-an-infinite-almost-arithmetic-progression%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Do you require the terms to be distinct? Also, since the gaps are allowed to grow unboundedly large, in what sense is this kind of sequence similar to an arithmetical progression? If the gaps are allowed to grow, then as Wojowu writes you are really just asking for the asymptotic growth rate of the primes, in a sense.
$endgroup$
– Carl Mummert
Mar 22 at 16:49
$begingroup$
@CarlMummert It was just a poorly thought out question, off the top of my head; I posted it too quickly. I am mulling some similar questions, e.g., about "almost geometric sequences" which might be a little less absurd. I might post that question if it doesn't turn into a pumpkin overnight.
$endgroup$
– Zach Teitler
Mar 23 at 6:50