Sets which are both Sum-free and Product-free.
$begingroup$
Let $P_o$ be the primes excluding $2$. $P_o subset mathbb{N}$ has the following property $Q$:
- For any $a,b in P_o$, $a + b notin P_o$.
- For any $a,b in P_o$, $ab notin P_o$.
So both addition and multiplication necessarily leave the set $P_o$.
$P_o$ has natural density $0$.
Q1. Is there a set $S subset mathbb{N}$ with positive density
that satisfies property $Q$?
Answered quickly by @JoséCarlosSantos: Yes.
Permit me then to add a new question:
Q2. What is largest density $S subset mathbb{N}$
that satisfies property $Q$?
Santos's example has density $frac{1}{3}$.
number-theory elementary-number-theory prime-numbers infinity
$endgroup$
add a comment |
$begingroup$
Let $P_o$ be the primes excluding $2$. $P_o subset mathbb{N}$ has the following property $Q$:
- For any $a,b in P_o$, $a + b notin P_o$.
- For any $a,b in P_o$, $ab notin P_o$.
So both addition and multiplication necessarily leave the set $P_o$.
$P_o$ has natural density $0$.
Q1. Is there a set $S subset mathbb{N}$ with positive density
that satisfies property $Q$?
Answered quickly by @JoséCarlosSantos: Yes.
Permit me then to add a new question:
Q2. What is largest density $S subset mathbb{N}$
that satisfies property $Q$?
Santos's example has density $frac{1}{3}$.
number-theory elementary-number-theory prime-numbers infinity
$endgroup$
1
$begingroup$
The title of this question seems very different from the body. (Did you maybe realize on your own, while writing the body, that the answer to the title was "No", and then adjust the body to be a new/more interesting question on the theme?)
$endgroup$
– ruakh
2 hours ago
add a comment |
$begingroup$
Let $P_o$ be the primes excluding $2$. $P_o subset mathbb{N}$ has the following property $Q$:
- For any $a,b in P_o$, $a + b notin P_o$.
- For any $a,b in P_o$, $ab notin P_o$.
So both addition and multiplication necessarily leave the set $P_o$.
$P_o$ has natural density $0$.
Q1. Is there a set $S subset mathbb{N}$ with positive density
that satisfies property $Q$?
Answered quickly by @JoséCarlosSantos: Yes.
Permit me then to add a new question:
Q2. What is largest density $S subset mathbb{N}$
that satisfies property $Q$?
Santos's example has density $frac{1}{3}$.
number-theory elementary-number-theory prime-numbers infinity
$endgroup$
Let $P_o$ be the primes excluding $2$. $P_o subset mathbb{N}$ has the following property $Q$:
- For any $a,b in P_o$, $a + b notin P_o$.
- For any $a,b in P_o$, $ab notin P_o$.
So both addition and multiplication necessarily leave the set $P_o$.
$P_o$ has natural density $0$.
Q1. Is there a set $S subset mathbb{N}$ with positive density
that satisfies property $Q$?
Answered quickly by @JoséCarlosSantos: Yes.
Permit me then to add a new question:
Q2. What is largest density $S subset mathbb{N}$
that satisfies property $Q$?
Santos's example has density $frac{1}{3}$.
number-theory elementary-number-theory prime-numbers infinity
number-theory elementary-number-theory prime-numbers infinity
edited 16 mins ago
Shalop
9,33911030
9,33911030
asked 9 hours ago
Joseph O'RourkeJoseph O'Rourke
18.1k349110
18.1k349110
1
$begingroup$
The title of this question seems very different from the body. (Did you maybe realize on your own, while writing the body, that the answer to the title was "No", and then adjust the body to be a new/more interesting question on the theme?)
$endgroup$
– ruakh
2 hours ago
add a comment |
1
$begingroup$
The title of this question seems very different from the body. (Did you maybe realize on your own, while writing the body, that the answer to the title was "No", and then adjust the body to be a new/more interesting question on the theme?)
$endgroup$
– ruakh
2 hours ago
1
1
$begingroup$
The title of this question seems very different from the body. (Did you maybe realize on your own, while writing the body, that the answer to the title was "No", and then adjust the body to be a new/more interesting question on the theme?)
$endgroup$
– ruakh
2 hours ago
$begingroup$
The title of this question seems very different from the body. (Did you maybe realize on your own, while writing the body, that the answer to the title was "No", and then adjust the body to be a new/more interesting question on the theme?)
$endgroup$
– ruakh
2 hours ago
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
add a comment |
$begingroup$
Let $S = {n : n equiv 2 rm{or} 3 pmod 5}$. This has density $2/5$, which beats $1/3$.
Incidentally, this sequence can be generated with a greedy algorithm, starting with $S = {2}$ and progressively adding every larger number that maintains the requirement.
$endgroup$
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
2
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
1
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
2
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
add a comment |
$begingroup$
This did not begin as an answer, but see edit below.
See this talk by Carl Pomerance, on sum-free sets, and product-free sets. One way to answer the OP (and this is the approach of the other answers) is to choose an $n$, and a subset $S$ of $mathbb{Z}/nmathbb{Z}$, such that $S$ is both sum-free (if $a,bin S$, then $a+bnotin S$) and product-free (if $a,bin S$, then $abnotin S$) . Then, we take all integers that are congruent to an element of $S$, modulo $n$. The desired asymptotic density is seen to be $frac{|S|}{n}$.
This might not be a simple question at all. Looking just at the sum-free property , we can easily get asymptotic density $0.5$ by taking the odd numbers. The product-free property is quite subtle: the linked talk gives a construction of a very large $n$ (with over 100 million digits) such that there is an $S$ satisfying $frac{|S|}{n}>0.5003$. In fact, we could raise $0.5003$ to be arbitrarily close to $1$ (although no construction is given in the linked talk). The general approach is to make $n$ have many small primes, to large powers, as factors.
One would not expect that this product-free set is also sum-free, but we can always remove some elements from it, until we have a subset of $S$ that is both sum-free and product-free. I have no idea how big that resulting subset would be.
EDIT: Following the methods of the linked talk, choose $n$ (assumed even) and product-free $S$, so that $frac{|S|}{n}ge 1-epsilon$. Hence $|S|ge n(1-epsilon)$. $S$ contains at most $frac{n}{2}$ even numbers (since $Ssubseteq {0,1,ldots, n-1}$, half of which are even). Take $T$ to be the set of all the odd numbers in $S$. We have $|T|ge |S|-frac{n}{2}=n(frac{1}{2}-epsilon)$. Since $Tsubseteq S$, $T$ is product-free. $T$ is also sum-free, since the sum of two elements of $T$ are even (and hence not in $T$). The asymptotic density of all naturals congruent to an element of $T$ modulo $n$ is $frac{|T|}{n}ge frac{1}{2}-epsilon$.
Note that an asymptotic density of $frac{1}{2}$ is best-possible for sum-free sets (as proved in Pomerance's slides), much less sum-free product-free sets. The above construction gives a subset of $mathbb{N}$ arbitrarily close to this bound.
$endgroup$
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
add a comment |
$begingroup$
New answer:
This paper answers the question. The upper density of any such set is strictly less than 1/2, but can be arbitrarily close to 1/2. I don't see that they state this explicitly in the paper, but it follows pretty quickly from Theorem 1.3.
Explicitly: Theorem 1.3 implies that for any $varepsilon>0$ there is some $n$ and some subset $Ssubsetmathbb{Z}/nmathbb{Z}$ of residue classes that is sum-free and product-free consisting of at least $(frac{1}{2}-varepsilon)n$ classes. Then taking all integers in those residue classes gives a product-free sum-free set of integers of density at least $(frac{1}{2}-varepsilon)$.
Old answer:
This talk cites the following result of Deshouillers, Freiman, S'{o}s and Temkin (1999):
If $Ssubseteq[n]$ is sum-free then at least one of the following holds:
- $lvert Srvertle2n/5+1$
$S$ consists of odds
$lvert Srvertlemin(S)$.
Therefore, if the density of a sum-free product-free set $P$ of integers is greater than 2/5, then $Pcap[n]$ must fall in the second case for sufficiently large $n$. (We can't be in the third case because $min(P)<2n/5$ for sufficiently large $n$.)
So, the only way we could hope to do better than 2/5 is to use only odd numbers, and as a corollary the highest density we could hope for is 1/2.
In fact, the proof of Remark 2.7 from this paper carries over to the case of only odd numbers, showing that we cannot attain a density of 1/2. For completeness, we repeat the argument here with the appropriate modifications: Let $a$ denote the least element of $P$, and let $P(x):=Pcap[1,x]$. Since $P(x)setminus{P(x/a)}$ lies in $(x/a,x]$, $lvert P(x)rvertle lvert P(x/a)rvert+frac{x-lfloor x/arfloor}{2}+1$. Also, multiplying each member of $P(x/a)$ creates products in $[1,x]$ which cannot lie in $P$, so we have $lvert P(x)rvertle frac{x}{2}+1-lvert P(x/a)rvert$. Adding these two inequalities and dividing both sides by 2 gives $lvert P(x)rvertle
frac{x}{2}-frac{lfloor x/arfloor}{2}+2$, which implies that the upper density of $P$ is at most $frac{1}{2}-frac{1}{2a}$.
$endgroup$
add a comment |
$begingroup$
The answer to the title question is no. $Q$ doesn't characterize the odd primes, since, for example, ${2,3,15}vDash Q$. Any subset of the odd primes satisfies $Q$, as does any set formed by taking the odd primes along with an even integer $k$ and deleting one of every pair of primes that differ by $k$. Or forget about the primes altogether and take any (finite or infinite) set ${a_1, a_2, dots}$ such that $2leq a_1 < a_2$ and, for all $i>2$, $a_i > a_{i-1}a_{i-2}$.
$endgroup$
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
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%2f3121694%2fsets-which-are-both-sum-free-and-product-free%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
add a comment |
$begingroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
add a comment |
$begingroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
answered 9 hours ago
José Carlos SantosJosé Carlos Santos
163k22130233
163k22130233
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
add a comment |
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
7 hours ago
add a comment |
$begingroup$
Let $S = {n : n equiv 2 rm{or} 3 pmod 5}$. This has density $2/5$, which beats $1/3$.
Incidentally, this sequence can be generated with a greedy algorithm, starting with $S = {2}$ and progressively adding every larger number that maintains the requirement.
$endgroup$
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
2
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
1
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
2
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
add a comment |
$begingroup$
Let $S = {n : n equiv 2 rm{or} 3 pmod 5}$. This has density $2/5$, which beats $1/3$.
Incidentally, this sequence can be generated with a greedy algorithm, starting with $S = {2}$ and progressively adding every larger number that maintains the requirement.
$endgroup$
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
2
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
1
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
2
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
add a comment |
$begingroup$
Let $S = {n : n equiv 2 rm{or} 3 pmod 5}$. This has density $2/5$, which beats $1/3$.
Incidentally, this sequence can be generated with a greedy algorithm, starting with $S = {2}$ and progressively adding every larger number that maintains the requirement.
$endgroup$
Let $S = {n : n equiv 2 rm{or} 3 pmod 5}$. This has density $2/5$, which beats $1/3$.
Incidentally, this sequence can be generated with a greedy algorithm, starting with $S = {2}$ and progressively adding every larger number that maintains the requirement.
answered 8 hours ago
ThéophileThéophile
19.9k12946
19.9k12946
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
2
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
1
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
2
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
add a comment |
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
2
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
1
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
2
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
7 hours ago
2
2
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
$begingroup$
@JosephO'Rourke Not necessarily: using a greedy algorithm starting at $1$ instead of $2$ leads to a different sequence that is not as dense: ${1, 3, 5, 7, 11, 13, 17, 19, 23, 27, 29, 31, 37, 41, 43, 45, 47, 53, 59, 61, ldots}$. (I'm surprised not to find this on OEIS. You might be interested in adding it there.) Other starting points are similarly bad. But it's interesting that the greedy method starting at $2$ gives a consistent structure, and I agree that it feels like it could be the best result.
$endgroup$
– Théophile
6 hours ago
6
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
6 hours ago
1
1
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
$begingroup$
@Théophile What it looks like you are doing is starting with 3 and running the greedy algorithm while restricting yourself to odd numbers; this will result in the set of odd numbers with an odd number of prime factors
$endgroup$
– alphacapture
5 hours ago
2
2
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
$begingroup$
@alphacapture, indeed, dropping the $1$ and checking OEIS for the rest gives oeis.org/A067019 . (It's generally a good idea to drop a few early terms when checking OEIS, especially $1$'s and $0$'s.)
$endgroup$
– Barry Cipra
3 hours ago
add a comment |
$begingroup$
This did not begin as an answer, but see edit below.
See this talk by Carl Pomerance, on sum-free sets, and product-free sets. One way to answer the OP (and this is the approach of the other answers) is to choose an $n$, and a subset $S$ of $mathbb{Z}/nmathbb{Z}$, such that $S$ is both sum-free (if $a,bin S$, then $a+bnotin S$) and product-free (if $a,bin S$, then $abnotin S$) . Then, we take all integers that are congruent to an element of $S$, modulo $n$. The desired asymptotic density is seen to be $frac{|S|}{n}$.
This might not be a simple question at all. Looking just at the sum-free property , we can easily get asymptotic density $0.5$ by taking the odd numbers. The product-free property is quite subtle: the linked talk gives a construction of a very large $n$ (with over 100 million digits) such that there is an $S$ satisfying $frac{|S|}{n}>0.5003$. In fact, we could raise $0.5003$ to be arbitrarily close to $1$ (although no construction is given in the linked talk). The general approach is to make $n$ have many small primes, to large powers, as factors.
One would not expect that this product-free set is also sum-free, but we can always remove some elements from it, until we have a subset of $S$ that is both sum-free and product-free. I have no idea how big that resulting subset would be.
EDIT: Following the methods of the linked talk, choose $n$ (assumed even) and product-free $S$, so that $frac{|S|}{n}ge 1-epsilon$. Hence $|S|ge n(1-epsilon)$. $S$ contains at most $frac{n}{2}$ even numbers (since $Ssubseteq {0,1,ldots, n-1}$, half of which are even). Take $T$ to be the set of all the odd numbers in $S$. We have $|T|ge |S|-frac{n}{2}=n(frac{1}{2}-epsilon)$. Since $Tsubseteq S$, $T$ is product-free. $T$ is also sum-free, since the sum of two elements of $T$ are even (and hence not in $T$). The asymptotic density of all naturals congruent to an element of $T$ modulo $n$ is $frac{|T|}{n}ge frac{1}{2}-epsilon$.
Note that an asymptotic density of $frac{1}{2}$ is best-possible for sum-free sets (as proved in Pomerance's slides), much less sum-free product-free sets. The above construction gives a subset of $mathbb{N}$ arbitrarily close to this bound.
$endgroup$
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
add a comment |
$begingroup$
This did not begin as an answer, but see edit below.
See this talk by Carl Pomerance, on sum-free sets, and product-free sets. One way to answer the OP (and this is the approach of the other answers) is to choose an $n$, and a subset $S$ of $mathbb{Z}/nmathbb{Z}$, such that $S$ is both sum-free (if $a,bin S$, then $a+bnotin S$) and product-free (if $a,bin S$, then $abnotin S$) . Then, we take all integers that are congruent to an element of $S$, modulo $n$. The desired asymptotic density is seen to be $frac{|S|}{n}$.
This might not be a simple question at all. Looking just at the sum-free property , we can easily get asymptotic density $0.5$ by taking the odd numbers. The product-free property is quite subtle: the linked talk gives a construction of a very large $n$ (with over 100 million digits) such that there is an $S$ satisfying $frac{|S|}{n}>0.5003$. In fact, we could raise $0.5003$ to be arbitrarily close to $1$ (although no construction is given in the linked talk). The general approach is to make $n$ have many small primes, to large powers, as factors.
One would not expect that this product-free set is also sum-free, but we can always remove some elements from it, until we have a subset of $S$ that is both sum-free and product-free. I have no idea how big that resulting subset would be.
EDIT: Following the methods of the linked talk, choose $n$ (assumed even) and product-free $S$, so that $frac{|S|}{n}ge 1-epsilon$. Hence $|S|ge n(1-epsilon)$. $S$ contains at most $frac{n}{2}$ even numbers (since $Ssubseteq {0,1,ldots, n-1}$, half of which are even). Take $T$ to be the set of all the odd numbers in $S$. We have $|T|ge |S|-frac{n}{2}=n(frac{1}{2}-epsilon)$. Since $Tsubseteq S$, $T$ is product-free. $T$ is also sum-free, since the sum of two elements of $T$ are even (and hence not in $T$). The asymptotic density of all naturals congruent to an element of $T$ modulo $n$ is $frac{|T|}{n}ge frac{1}{2}-epsilon$.
Note that an asymptotic density of $frac{1}{2}$ is best-possible for sum-free sets (as proved in Pomerance's slides), much less sum-free product-free sets. The above construction gives a subset of $mathbb{N}$ arbitrarily close to this bound.
$endgroup$
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
add a comment |
$begingroup$
This did not begin as an answer, but see edit below.
See this talk by Carl Pomerance, on sum-free sets, and product-free sets. One way to answer the OP (and this is the approach of the other answers) is to choose an $n$, and a subset $S$ of $mathbb{Z}/nmathbb{Z}$, such that $S$ is both sum-free (if $a,bin S$, then $a+bnotin S$) and product-free (if $a,bin S$, then $abnotin S$) . Then, we take all integers that are congruent to an element of $S$, modulo $n$. The desired asymptotic density is seen to be $frac{|S|}{n}$.
This might not be a simple question at all. Looking just at the sum-free property , we can easily get asymptotic density $0.5$ by taking the odd numbers. The product-free property is quite subtle: the linked talk gives a construction of a very large $n$ (with over 100 million digits) such that there is an $S$ satisfying $frac{|S|}{n}>0.5003$. In fact, we could raise $0.5003$ to be arbitrarily close to $1$ (although no construction is given in the linked talk). The general approach is to make $n$ have many small primes, to large powers, as factors.
One would not expect that this product-free set is also sum-free, but we can always remove some elements from it, until we have a subset of $S$ that is both sum-free and product-free. I have no idea how big that resulting subset would be.
EDIT: Following the methods of the linked talk, choose $n$ (assumed even) and product-free $S$, so that $frac{|S|}{n}ge 1-epsilon$. Hence $|S|ge n(1-epsilon)$. $S$ contains at most $frac{n}{2}$ even numbers (since $Ssubseteq {0,1,ldots, n-1}$, half of which are even). Take $T$ to be the set of all the odd numbers in $S$. We have $|T|ge |S|-frac{n}{2}=n(frac{1}{2}-epsilon)$. Since $Tsubseteq S$, $T$ is product-free. $T$ is also sum-free, since the sum of two elements of $T$ are even (and hence not in $T$). The asymptotic density of all naturals congruent to an element of $T$ modulo $n$ is $frac{|T|}{n}ge frac{1}{2}-epsilon$.
Note that an asymptotic density of $frac{1}{2}$ is best-possible for sum-free sets (as proved in Pomerance's slides), much less sum-free product-free sets. The above construction gives a subset of $mathbb{N}$ arbitrarily close to this bound.
$endgroup$
This did not begin as an answer, but see edit below.
See this talk by Carl Pomerance, on sum-free sets, and product-free sets. One way to answer the OP (and this is the approach of the other answers) is to choose an $n$, and a subset $S$ of $mathbb{Z}/nmathbb{Z}$, such that $S$ is both sum-free (if $a,bin S$, then $a+bnotin S$) and product-free (if $a,bin S$, then $abnotin S$) . Then, we take all integers that are congruent to an element of $S$, modulo $n$. The desired asymptotic density is seen to be $frac{|S|}{n}$.
This might not be a simple question at all. Looking just at the sum-free property , we can easily get asymptotic density $0.5$ by taking the odd numbers. The product-free property is quite subtle: the linked talk gives a construction of a very large $n$ (with over 100 million digits) such that there is an $S$ satisfying $frac{|S|}{n}>0.5003$. In fact, we could raise $0.5003$ to be arbitrarily close to $1$ (although no construction is given in the linked talk). The general approach is to make $n$ have many small primes, to large powers, as factors.
One would not expect that this product-free set is also sum-free, but we can always remove some elements from it, until we have a subset of $S$ that is both sum-free and product-free. I have no idea how big that resulting subset would be.
EDIT: Following the methods of the linked talk, choose $n$ (assumed even) and product-free $S$, so that $frac{|S|}{n}ge 1-epsilon$. Hence $|S|ge n(1-epsilon)$. $S$ contains at most $frac{n}{2}$ even numbers (since $Ssubseteq {0,1,ldots, n-1}$, half of which are even). Take $T$ to be the set of all the odd numbers in $S$. We have $|T|ge |S|-frac{n}{2}=n(frac{1}{2}-epsilon)$. Since $Tsubseteq S$, $T$ is product-free. $T$ is also sum-free, since the sum of two elements of $T$ are even (and hence not in $T$). The asymptotic density of all naturals congruent to an element of $T$ modulo $n$ is $frac{|T|}{n}ge frac{1}{2}-epsilon$.
Note that an asymptotic density of $frac{1}{2}$ is best-possible for sum-free sets (as proved in Pomerance's slides), much less sum-free product-free sets. The above construction gives a subset of $mathbb{N}$ arbitrarily close to this bound.
edited 2 hours ago
answered 4 hours ago
vadim123vadim123
76.2k897190
76.2k897190
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
add a comment |
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
4 hours ago
add a comment |
$begingroup$
New answer:
This paper answers the question. The upper density of any such set is strictly less than 1/2, but can be arbitrarily close to 1/2. I don't see that they state this explicitly in the paper, but it follows pretty quickly from Theorem 1.3.
Explicitly: Theorem 1.3 implies that for any $varepsilon>0$ there is some $n$ and some subset $Ssubsetmathbb{Z}/nmathbb{Z}$ of residue classes that is sum-free and product-free consisting of at least $(frac{1}{2}-varepsilon)n$ classes. Then taking all integers in those residue classes gives a product-free sum-free set of integers of density at least $(frac{1}{2}-varepsilon)$.
Old answer:
This talk cites the following result of Deshouillers, Freiman, S'{o}s and Temkin (1999):
If $Ssubseteq[n]$ is sum-free then at least one of the following holds:
- $lvert Srvertle2n/5+1$
$S$ consists of odds
$lvert Srvertlemin(S)$.
Therefore, if the density of a sum-free product-free set $P$ of integers is greater than 2/5, then $Pcap[n]$ must fall in the second case for sufficiently large $n$. (We can't be in the third case because $min(P)<2n/5$ for sufficiently large $n$.)
So, the only way we could hope to do better than 2/5 is to use only odd numbers, and as a corollary the highest density we could hope for is 1/2.
In fact, the proof of Remark 2.7 from this paper carries over to the case of only odd numbers, showing that we cannot attain a density of 1/2. For completeness, we repeat the argument here with the appropriate modifications: Let $a$ denote the least element of $P$, and let $P(x):=Pcap[1,x]$. Since $P(x)setminus{P(x/a)}$ lies in $(x/a,x]$, $lvert P(x)rvertle lvert P(x/a)rvert+frac{x-lfloor x/arfloor}{2}+1$. Also, multiplying each member of $P(x/a)$ creates products in $[1,x]$ which cannot lie in $P$, so we have $lvert P(x)rvertle frac{x}{2}+1-lvert P(x/a)rvert$. Adding these two inequalities and dividing both sides by 2 gives $lvert P(x)rvertle
frac{x}{2}-frac{lfloor x/arfloor}{2}+2$, which implies that the upper density of $P$ is at most $frac{1}{2}-frac{1}{2a}$.
$endgroup$
add a comment |
$begingroup$
New answer:
This paper answers the question. The upper density of any such set is strictly less than 1/2, but can be arbitrarily close to 1/2. I don't see that they state this explicitly in the paper, but it follows pretty quickly from Theorem 1.3.
Explicitly: Theorem 1.3 implies that for any $varepsilon>0$ there is some $n$ and some subset $Ssubsetmathbb{Z}/nmathbb{Z}$ of residue classes that is sum-free and product-free consisting of at least $(frac{1}{2}-varepsilon)n$ classes. Then taking all integers in those residue classes gives a product-free sum-free set of integers of density at least $(frac{1}{2}-varepsilon)$.
Old answer:
This talk cites the following result of Deshouillers, Freiman, S'{o}s and Temkin (1999):
If $Ssubseteq[n]$ is sum-free then at least one of the following holds:
- $lvert Srvertle2n/5+1$
$S$ consists of odds
$lvert Srvertlemin(S)$.
Therefore, if the density of a sum-free product-free set $P$ of integers is greater than 2/5, then $Pcap[n]$ must fall in the second case for sufficiently large $n$. (We can't be in the third case because $min(P)<2n/5$ for sufficiently large $n$.)
So, the only way we could hope to do better than 2/5 is to use only odd numbers, and as a corollary the highest density we could hope for is 1/2.
In fact, the proof of Remark 2.7 from this paper carries over to the case of only odd numbers, showing that we cannot attain a density of 1/2. For completeness, we repeat the argument here with the appropriate modifications: Let $a$ denote the least element of $P$, and let $P(x):=Pcap[1,x]$. Since $P(x)setminus{P(x/a)}$ lies in $(x/a,x]$, $lvert P(x)rvertle lvert P(x/a)rvert+frac{x-lfloor x/arfloor}{2}+1$. Also, multiplying each member of $P(x/a)$ creates products in $[1,x]$ which cannot lie in $P$, so we have $lvert P(x)rvertle frac{x}{2}+1-lvert P(x/a)rvert$. Adding these two inequalities and dividing both sides by 2 gives $lvert P(x)rvertle
frac{x}{2}-frac{lfloor x/arfloor}{2}+2$, which implies that the upper density of $P$ is at most $frac{1}{2}-frac{1}{2a}$.
$endgroup$
add a comment |
$begingroup$
New answer:
This paper answers the question. The upper density of any such set is strictly less than 1/2, but can be arbitrarily close to 1/2. I don't see that they state this explicitly in the paper, but it follows pretty quickly from Theorem 1.3.
Explicitly: Theorem 1.3 implies that for any $varepsilon>0$ there is some $n$ and some subset $Ssubsetmathbb{Z}/nmathbb{Z}$ of residue classes that is sum-free and product-free consisting of at least $(frac{1}{2}-varepsilon)n$ classes. Then taking all integers in those residue classes gives a product-free sum-free set of integers of density at least $(frac{1}{2}-varepsilon)$.
Old answer:
This talk cites the following result of Deshouillers, Freiman, S'{o}s and Temkin (1999):
If $Ssubseteq[n]$ is sum-free then at least one of the following holds:
- $lvert Srvertle2n/5+1$
$S$ consists of odds
$lvert Srvertlemin(S)$.
Therefore, if the density of a sum-free product-free set $P$ of integers is greater than 2/5, then $Pcap[n]$ must fall in the second case for sufficiently large $n$. (We can't be in the third case because $min(P)<2n/5$ for sufficiently large $n$.)
So, the only way we could hope to do better than 2/5 is to use only odd numbers, and as a corollary the highest density we could hope for is 1/2.
In fact, the proof of Remark 2.7 from this paper carries over to the case of only odd numbers, showing that we cannot attain a density of 1/2. For completeness, we repeat the argument here with the appropriate modifications: Let $a$ denote the least element of $P$, and let $P(x):=Pcap[1,x]$. Since $P(x)setminus{P(x/a)}$ lies in $(x/a,x]$, $lvert P(x)rvertle lvert P(x/a)rvert+frac{x-lfloor x/arfloor}{2}+1$. Also, multiplying each member of $P(x/a)$ creates products in $[1,x]$ which cannot lie in $P$, so we have $lvert P(x)rvertle frac{x}{2}+1-lvert P(x/a)rvert$. Adding these two inequalities and dividing both sides by 2 gives $lvert P(x)rvertle
frac{x}{2}-frac{lfloor x/arfloor}{2}+2$, which implies that the upper density of $P$ is at most $frac{1}{2}-frac{1}{2a}$.
$endgroup$
New answer:
This paper answers the question. The upper density of any such set is strictly less than 1/2, but can be arbitrarily close to 1/2. I don't see that they state this explicitly in the paper, but it follows pretty quickly from Theorem 1.3.
Explicitly: Theorem 1.3 implies that for any $varepsilon>0$ there is some $n$ and some subset $Ssubsetmathbb{Z}/nmathbb{Z}$ of residue classes that is sum-free and product-free consisting of at least $(frac{1}{2}-varepsilon)n$ classes. Then taking all integers in those residue classes gives a product-free sum-free set of integers of density at least $(frac{1}{2}-varepsilon)$.
Old answer:
This talk cites the following result of Deshouillers, Freiman, S'{o}s and Temkin (1999):
If $Ssubseteq[n]$ is sum-free then at least one of the following holds:
- $lvert Srvertle2n/5+1$
$S$ consists of odds
$lvert Srvertlemin(S)$.
Therefore, if the density of a sum-free product-free set $P$ of integers is greater than 2/5, then $Pcap[n]$ must fall in the second case for sufficiently large $n$. (We can't be in the third case because $min(P)<2n/5$ for sufficiently large $n$.)
So, the only way we could hope to do better than 2/5 is to use only odd numbers, and as a corollary the highest density we could hope for is 1/2.
In fact, the proof of Remark 2.7 from this paper carries over to the case of only odd numbers, showing that we cannot attain a density of 1/2. For completeness, we repeat the argument here with the appropriate modifications: Let $a$ denote the least element of $P$, and let $P(x):=Pcap[1,x]$. Since $P(x)setminus{P(x/a)}$ lies in $(x/a,x]$, $lvert P(x)rvertle lvert P(x/a)rvert+frac{x-lfloor x/arfloor}{2}+1$. Also, multiplying each member of $P(x/a)$ creates products in $[1,x]$ which cannot lie in $P$, so we have $lvert P(x)rvertle frac{x}{2}+1-lvert P(x/a)rvert$. Adding these two inequalities and dividing both sides by 2 gives $lvert P(x)rvertle
frac{x}{2}-frac{lfloor x/arfloor}{2}+2$, which implies that the upper density of $P$ is at most $frac{1}{2}-frac{1}{2a}$.
edited 1 hour ago
answered 3 hours ago
alphacapturealphacapture
2,021422
2,021422
add a comment |
add a comment |
$begingroup$
The answer to the title question is no. $Q$ doesn't characterize the odd primes, since, for example, ${2,3,15}vDash Q$. Any subset of the odd primes satisfies $Q$, as does any set formed by taking the odd primes along with an even integer $k$ and deleting one of every pair of primes that differ by $k$. Or forget about the primes altogether and take any (finite or infinite) set ${a_1, a_2, dots}$ such that $2leq a_1 < a_2$ and, for all $i>2$, $a_i > a_{i-1}a_{i-2}$.
$endgroup$
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
add a comment |
$begingroup$
The answer to the title question is no. $Q$ doesn't characterize the odd primes, since, for example, ${2,3,15}vDash Q$. Any subset of the odd primes satisfies $Q$, as does any set formed by taking the odd primes along with an even integer $k$ and deleting one of every pair of primes that differ by $k$. Or forget about the primes altogether and take any (finite or infinite) set ${a_1, a_2, dots}$ such that $2leq a_1 < a_2$ and, for all $i>2$, $a_i > a_{i-1}a_{i-2}$.
$endgroup$
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
add a comment |
$begingroup$
The answer to the title question is no. $Q$ doesn't characterize the odd primes, since, for example, ${2,3,15}vDash Q$. Any subset of the odd primes satisfies $Q$, as does any set formed by taking the odd primes along with an even integer $k$ and deleting one of every pair of primes that differ by $k$. Or forget about the primes altogether and take any (finite or infinite) set ${a_1, a_2, dots}$ such that $2leq a_1 < a_2$ and, for all $i>2$, $a_i > a_{i-1}a_{i-2}$.
$endgroup$
The answer to the title question is no. $Q$ doesn't characterize the odd primes, since, for example, ${2,3,15}vDash Q$. Any subset of the odd primes satisfies $Q$, as does any set formed by taking the odd primes along with an even integer $k$ and deleting one of every pair of primes that differ by $k$. Or forget about the primes altogether and take any (finite or infinite) set ${a_1, a_2, dots}$ such that $2leq a_1 < a_2$ and, for all $i>2$, $a_i > a_{i-1}a_{i-2}$.
answered 3 hours ago
David RicherbyDavid Richerby
2,16111324
2,16111324
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
add a comment |
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
2
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
3 hours ago
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%2f3121694%2fsets-which-are-both-sum-free-and-product-free%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$
The title of this question seems very different from the body. (Did you maybe realize on your own, while writing the body, that the answer to the title was "No", and then adjust the body to be a new/more interesting question on the theme?)
$endgroup$
– ruakh
2 hours ago