Is there a set of positive integers of density 1 which contains no infinite arithmetic progression?Density of a set of natural numbers whose differences are not bounded.What is the shortest route to Roth's theorem?Inverse Length 3 Arithmetic Progression Problem for sets with positive upper densityDo there exist sets of integers with arbitrarily large upper density which contains infinitely many elements that are not in an arithmetic progression of length 3?Arithmetic progressions in power sequencesAre there infinite primes among powerful order terms of Dirichlet arithmetic progressions?every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?On the upper Banach density of the set of positive integers whose base-$b$ representation misses at least one prescribed digitAdditivity of upper densities with respect to arithmetic progressions of integersExistence of Arithmetic Progression from density inequalityDiscrepancy in non-homogeneous arithmetic progressions
Is there a set of positive integers of density 1 which contains no infinite arithmetic progression?
Density of a set of natural numbers whose differences are not bounded.What is the shortest route to Roth's theorem?Inverse Length 3 Arithmetic Progression Problem for sets with positive upper densityDo there exist sets of integers with arbitrarily large upper density which contains infinitely many elements that are not in an arithmetic progression of length 3?Arithmetic progressions in power sequencesAre there infinite primes among powerful order terms of Dirichlet arithmetic progressions?every arithmetic progression contains a sequence of $k$ “consecutive” primes for possibly all natural numbers $k$?On the upper Banach density of the set of positive integers whose base-$b$ representation misses at least one prescribed digitAdditivity of upper densities with respect to arithmetic progressions of integersExistence of Arithmetic Progression from density inequalityDiscrepancy in non-homogeneous arithmetic progressions
$begingroup$
Let $V$ be a set of positive integers whose natural density is 1. Is it necessarily true that $V$ contains an infinite arithmetic progression?—i.e., that there are non-negative integers $a,b,nu$ with $0leq bleq a-1$ so that: $$left an+b:ngeqnuright subseteq V$$
In addition to an answer, any references on the matter would be most appreciated.
nt.number-theory additive-combinatorics
asked Jun 6 at 21:28
MCSMCS
313111
$endgroup$
add a comment |
$begingroup$
Let $V$ be a set of positive integers whose natural density is 1. Is it necessarily true that $V$ contains an infinite arithmetic progression?—i.e., that there are non-negative integers $a,b,nu$ with $0leq bleq a-1$ so that: $$left an+b:ngeqnuright subseteq V$$
In addition to an answer, any references on the matter would be most appreciated.
nt.number-theory additive-combinatorics
asked Jun 6 at 21:28
MCSMCS
313111
$endgroup$
26
$begingroup$
Enumerate all the arithmetic progressions as $A_n$. Now remove from $mathbb N$ the $2^n$-th element of $A_n$ for each $n$.
$endgroup$
– Wojowu
Jun 6 at 21:33
1
$begingroup$
So sets that contradict this exist? Excellent! Thank you. :)
$endgroup$
– MCS
Jun 6 at 21:35
8
$begingroup$
Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression.
$endgroup$
– Henry Cohn
Jun 6 at 22:49
7
$begingroup$
A more constructive way would be the following: Take any increasing function $f$, and put $V=mathbbNsetminusbigcup_ngeq 1 [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $mathbbNsetminus V$ arbitrary small.
$endgroup$
– Jan-Christoph Schlage-Puchta
Jun 7 at 12:35
$begingroup$
The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too.
$endgroup$
– Benjamin Dickman
Jun 9 at 18:45
add a comment |
$begingroup$
Let $V$ be a set of positive integers whose natural density is 1. Is it necessarily true that $V$ contains an infinite arithmetic progression?—i.e., that there are non-negative integers $a,b,nu$ with $0leq bleq a-1$ so that: $$left an+b:ngeqnuright subseteq V$$
In addition to an answer, any references on the matter would be most appreciated.
nt.number-theory additive-combinatorics
asked Jun 6 at 21:28
MCSMCS
313111
$endgroup$
Let $V$ be a set of positive integers whose natural density is 1. Is it necessarily true that $V$ contains an infinite arithmetic progression?—i.e., that there are non-negative integers $a,b,nu$ with $0leq bleq a-1$ so that: $$left an+b:ngeqnuright subseteq V$$
In addition to an answer, any references on the matter would be most appreciated.
nt.number-theory additive-combinatorics
nt.number-theory additive-combinatorics
asked Jun 6 at 21:28
MCSMCS
313111
asked Jun 6 at 21:28
MCSMCS
313111
asked Jun 6 at 21:28
MCSMCS
313111
asked Jun 6 at 21:28
MCSMCS
313111
asked Jun 6 at 21:28
MCSMCS
313111
313111
26
$begingroup$
Enumerate all the arithmetic progressions as $A_n$. Now remove from $mathbb N$ the $2^n$-th element of $A_n$ for each $n$.
$endgroup$
– Wojowu
Jun 6 at 21:33
1
$begingroup$
So sets that contradict this exist? Excellent! Thank you. :)
$endgroup$
– MCS
Jun 6 at 21:35
8
$begingroup$
Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression.
$endgroup$
– Henry Cohn
Jun 6 at 22:49
7
$begingroup$
A more constructive way would be the following: Take any increasing function $f$, and put $V=mathbbNsetminusbigcup_ngeq 1 [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $mathbbNsetminus V$ arbitrary small.
$endgroup$
– Jan-Christoph Schlage-Puchta
Jun 7 at 12:35
$begingroup$
The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too.
$endgroup$
– Benjamin Dickman
Jun 9 at 18:45
add a comment |
26
$begingroup$
Enumerate all the arithmetic progressions as $A_n$. Now remove from $mathbb N$ the $2^n$-th element of $A_n$ for each $n$.
$endgroup$
– Wojowu
Jun 6 at 21:33
1
$begingroup$
So sets that contradict this exist? Excellent! Thank you. :)
$endgroup$
– MCS
Jun 6 at 21:35
8
$begingroup$
Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression.
$endgroup$
– Henry Cohn
Jun 6 at 22:49
7
$begingroup$
A more constructive way would be the following: Take any increasing function $f$, and put $V=mathbbNsetminusbigcup_ngeq 1 [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $mathbbNsetminus V$ arbitrary small.
$endgroup$
– Jan-Christoph Schlage-Puchta
Jun 7 at 12:35
$begingroup$
The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too.
$endgroup$
– Benjamin Dickman
Jun 9 at 18:45
26
26
$begingroup$
Enumerate all the arithmetic progressions as $A_n$. Now remove from $mathbb N$ the $2^n$-th element of $A_n$ for each $n$.
$endgroup$
– Wojowu
Jun 6 at 21:33
$begingroup$
Enumerate all the arithmetic progressions as $A_n$. Now remove from $mathbb N$ the $2^n$-th element of $A_n$ for each $n$.
$endgroup$
– Wojowu
Jun 6 at 21:33
1
1
$begingroup$
So sets that contradict this exist? Excellent! Thank you. :)
$endgroup$
– MCS
Jun 6 at 21:35
$begingroup$
So sets that contradict this exist? Excellent! Thank you. :)
$endgroup$
– MCS
Jun 6 at 21:35
8
8
$begingroup$
Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression.
$endgroup$
– Henry Cohn
Jun 6 at 22:49
$begingroup$
Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression.
$endgroup$
– Henry Cohn
Jun 6 at 22:49
7
7
$begingroup$
A more constructive way would be the following: Take any increasing function $f$, and put $V=mathbbNsetminusbigcup_ngeq 1 [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $mathbbNsetminus V$ arbitrary small.
$endgroup$
– Jan-Christoph Schlage-Puchta
Jun 7 at 12:35
$begingroup$
A more constructive way would be the following: Take any increasing function $f$, and put $V=mathbbNsetminusbigcup_ngeq 1 [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $mathbbNsetminus V$ arbitrary small.
$endgroup$
– Jan-Christoph Schlage-Puchta
Jun 7 at 12:35
$begingroup$
The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too.
$endgroup$
– Benjamin Dickman
Jun 9 at 18:45
$begingroup$
The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too.
$endgroup$
– Benjamin Dickman
Jun 9 at 18:45
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Another construction is to let $n notin V$ if and only if $n$ begins with at least $sqrtlogn$ consecutive '9's when written in decimal. This satisfies the stronger property that there is no non-constant polynomial $f : mathbbN rightarrow mathbbN$ whose image is contained entirely in $V$.
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
$endgroup$
add a comment |
$begingroup$
Here is a concrete counterexample (where $mathbbN$ is the set of positive integers):
$$V:=mathbbNsetminusa^2b^2+b:a,binmathbbN.$$
It is straightforward to see that $V$ has density $1$, but it does not contain an infinite arithmetic progression.
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
$endgroup$
6
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
add a comment |
$begingroup$
Yet another concrete counterexample:
$$ bigcup_n=1^infty [n^3+n,(n+1)^3]. $$
More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $1$ if the gaps are properly spaced.
Incidentally, an incomparably subtler question is whether any set of positive natural density contains arbitrarily long arithmetic progressions. This was conjecture by Erdős and Turán in 1936 and famously proved by Szemerédi almost 40 years later.
edited Jun 7 at 20:11
GH from MO
61.1k5154234
answered Jun 7 at 12:28
SevaSeva
13.5k138105
$endgroup$
5
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
1
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
1
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
2
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
add a comment |
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "504"
;
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%2fmathoverflow.net%2fquestions%2f333430%2fis-there-a-set-of-positive-integers-of-density-1-which-contains-no-infinite-arit%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$
Another construction is to let $n notin V$ if and only if $n$ begins with at least $sqrtlogn$ consecutive '9's when written in decimal. This satisfies the stronger property that there is no non-constant polynomial $f : mathbbN rightarrow mathbbN$ whose image is contained entirely in $V$.
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
$endgroup$
add a comment |
$begingroup$
Another construction is to let $n notin V$ if and only if $n$ begins with at least $sqrtlogn$ consecutive '9's when written in decimal. This satisfies the stronger property that there is no non-constant polynomial $f : mathbbN rightarrow mathbbN$ whose image is contained entirely in $V$.
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
$endgroup$
add a comment |
$begingroup$
Another construction is to let $n notin V$ if and only if $n$ begins with at least $sqrtlogn$ consecutive '9's when written in decimal. This satisfies the stronger property that there is no non-constant polynomial $f : mathbbN rightarrow mathbbN$ whose image is contained entirely in $V$.
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
$endgroup$
Another construction is to let $n notin V$ if and only if $n$ begins with at least $sqrtlogn$ consecutive '9's when written in decimal. This satisfies the stronger property that there is no non-constant polynomial $f : mathbbN rightarrow mathbbN$ whose image is contained entirely in $V$.
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
answered Jun 7 at 13:34
Adam P. GoucherAdam P. Goucher
7,23523263
7,23523263
add a comment |
add a comment |
$begingroup$
Here is a concrete counterexample (where $mathbbN$ is the set of positive integers):
$$V:=mathbbNsetminusa^2b^2+b:a,binmathbbN.$$
It is straightforward to see that $V$ has density $1$, but it does not contain an infinite arithmetic progression.
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
$endgroup$
6
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
add a comment |
$begingroup$
Here is a concrete counterexample (where $mathbbN$ is the set of positive integers):
$$V:=mathbbNsetminusa^2b^2+b:a,binmathbbN.$$
It is straightforward to see that $V$ has density $1$, but it does not contain an infinite arithmetic progression.
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
$endgroup$
6
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
add a comment |
$begingroup$
Here is a concrete counterexample (where $mathbbN$ is the set of positive integers):
$$V:=mathbbNsetminusa^2b^2+b:a,binmathbbN.$$
It is straightforward to see that $V$ has density $1$, but it does not contain an infinite arithmetic progression.
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
$endgroup$
Here is a concrete counterexample (where $mathbbN$ is the set of positive integers):
$$V:=mathbbNsetminusa^2b^2+b:a,binmathbbN.$$
It is straightforward to see that $V$ has density $1$, but it does not contain an infinite arithmetic progression.
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
answered Jun 6 at 22:01
GH from MOGH from MO
61.1k5154234
61.1k5154234
6
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
add a comment |
6
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
6
6
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
$begingroup$
Here is a straightforward proof for anyone else who found the density non-obvious: In $(a,b):a^2b^2+b<N$, each value of $b$ has at most $sqrtN/b$ values of $a$. Also $b<sqrtN$. So the cardinality of the set is at most $$sum_b=1^sqrtN fracsqrtNb < 2int_1^sqrtN+1fracsqrtNbdb< 2sqrtNln(N)$$ Since $2sqrtNln(N)/Nrightarrow 0$, the density of these sets goes to 0.
$endgroup$
– Matt F.
Jun 7 at 19:04
add a comment |
$begingroup$
Yet another concrete counterexample:
$$ bigcup_n=1^infty [n^3+n,(n+1)^3]. $$
More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $1$ if the gaps are properly spaced.
Incidentally, an incomparably subtler question is whether any set of positive natural density contains arbitrarily long arithmetic progressions. This was conjecture by Erdős and Turán in 1936 and famously proved by Szemerédi almost 40 years later.
edited Jun 7 at 20:11
GH from MO
61.1k5154234
answered Jun 7 at 12:28
SevaSeva
13.5k138105
$endgroup$
5
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
1
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
1
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
2
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
add a comment |
$begingroup$
Yet another concrete counterexample:
$$ bigcup_n=1^infty [n^3+n,(n+1)^3]. $$
More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $1$ if the gaps are properly spaced.
Incidentally, an incomparably subtler question is whether any set of positive natural density contains arbitrarily long arithmetic progressions. This was conjecture by Erdős and Turán in 1936 and famously proved by Szemerédi almost 40 years later.
edited Jun 7 at 20:11
GH from MO
61.1k5154234
answered Jun 7 at 12:28
SevaSeva
13.5k138105
$endgroup$
5
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
1
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
1
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
2
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
add a comment |
$begingroup$
Yet another concrete counterexample:
$$ bigcup_n=1^infty [n^3+n,(n+1)^3]. $$
More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $1$ if the gaps are properly spaced.
Incidentally, an incomparably subtler question is whether any set of positive natural density contains arbitrarily long arithmetic progressions. This was conjecture by Erdős and Turán in 1936 and famously proved by Szemerédi almost 40 years later.
edited Jun 7 at 20:11
GH from MO
61.1k5154234
answered Jun 7 at 12:28
SevaSeva
13.5k138105
$endgroup$
Yet another concrete counterexample:
$$ bigcup_n=1^infty [n^3+n,(n+1)^3]. $$
More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $1$ if the gaps are properly spaced.
Incidentally, an incomparably subtler question is whether any set of positive natural density contains arbitrarily long arithmetic progressions. This was conjecture by Erdős and Turán in 1936 and famously proved by Szemerédi almost 40 years later.
edited Jun 7 at 20:11
GH from MO
61.1k5154234
answered Jun 7 at 12:28
SevaSeva
13.5k138105
edited Jun 7 at 20:11
GH from MO
61.1k5154234
edited Jun 7 at 20:11
GH from MO
61.1k5154234
edited Jun 7 at 20:11
GH from MO
61.1k5154234
61.1k5154234
answered Jun 7 at 12:28
SevaSeva
13.5k138105
answered Jun 7 at 12:28
SevaSeva
13.5k138105
answered Jun 7 at 12:28
SevaSeva
13.5k138105
13.5k138105
5
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
1
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
1
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
2
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
add a comment |
5
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
1
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
1
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
2
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
5
5
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
$begingroup$
Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$.
$endgroup$
– Wojowu
Jun 7 at 12:45
1
1
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
$begingroup$
I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded.
$endgroup$
– Martin Sleziak
Jun 7 at 12:51
1
1
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
$begingroup$
@Wojowu: absolutely - my bad; I have edited the answer.
$endgroup$
– Seva
Jun 7 at 12:58
2
2
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
$begingroup$
@Wojowu Doesn't Szemeredi's theorem just require positve upper density?
$endgroup$
– bof
Jun 7 at 15:46
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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%2fmathoverflow.net%2fquestions%2f333430%2fis-there-a-set-of-positive-integers-of-density-1-which-contains-no-infinite-arit%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
26
$begingroup$
Enumerate all the arithmetic progressions as $A_n$. Now remove from $mathbb N$ the $2^n$-th element of $A_n$ for each $n$.
$endgroup$
– Wojowu
Jun 6 at 21:33
1
$begingroup$
So sets that contradict this exist? Excellent! Thank you. :)
$endgroup$
– MCS
Jun 6 at 21:35
8
$begingroup$
Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression.
$endgroup$
– Henry Cohn
Jun 6 at 22:49
7
$begingroup$
A more constructive way would be the following: Take any increasing function $f$, and put $V=mathbbNsetminusbigcup_ngeq 1 [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $mathbbNsetminus V$ arbitrary small.
$endgroup$
– Jan-Christoph Schlage-Puchta
Jun 7 at 12:35
$begingroup$
The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too.
$endgroup$
– Benjamin Dickman
Jun 9 at 18:45