Sets that 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$
8
$begingroup$
Instead of adding a question after receiving an answer to your original question, you should ask that other question separately
$endgroup$
– Hagen von Eitzen
17 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 17 mins ago
Joseph O'Rourke
asked yesterday
Joseph O'RourkeJoseph O'Rourke
18.1k349111
18.1k349111
8
$begingroup$
Instead of adding a question after receiving an answer to your original question, you should ask that other question separately
$endgroup$
– Hagen von Eitzen
17 hours ago
add a comment |
8
$begingroup$
Instead of adding a question after receiving an answer to your original question, you should ask that other question separately
$endgroup$
– Hagen von Eitzen
17 hours ago
8
8
$begingroup$
Instead of adding a question after receiving an answer to your original question, you should ask that other question separately
$endgroup$
– Hagen von Eitzen
17 hours ago
$begingroup$
Instead of adding a question after receiving an answer to your original question, you should ask that other question separately
$endgroup$
– Hagen von Eitzen
17 hours ago
add a comment |
5 Answers
5
active
oldest
votes
$begingroup$
New answer:
Kurlberg, Lagarias and Pomerance, On sets of integers which are both sum-free and product-free (arXiv:1201.1317) 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:
Andrew Treglow's talk On sum-free and solution-free sets of integers cites the following result of Deshouillers, Freiman, Só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 of Kurlberg, Lagarias and Pomerance, Product-free sets with high density 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$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
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$
1
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
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
yesterday
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
yesterday
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
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
yesterday
3
$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
yesterday
|
show 1 more 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
yesterday
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-that-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$
New answer:
Kurlberg, Lagarias and Pomerance, On sets of integers which are both sum-free and product-free (arXiv:1201.1317) 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:
Andrew Treglow's talk On sum-free and solution-free sets of integers cites the following result of Deshouillers, Freiman, Só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 of Kurlberg, Lagarias and Pomerance, Product-free sets with high density 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:
Kurlberg, Lagarias and Pomerance, On sets of integers which are both sum-free and product-free (arXiv:1201.1317) 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:
Andrew Treglow's talk On sum-free and solution-free sets of integers cites the following result of Deshouillers, Freiman, Só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 of Kurlberg, Lagarias and Pomerance, Product-free sets with high density 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:
Kurlberg, Lagarias and Pomerance, On sets of integers which are both sum-free and product-free (arXiv:1201.1317) 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:
Andrew Treglow's talk On sum-free and solution-free sets of integers cites the following result of Deshouillers, Freiman, Só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 of Kurlberg, Lagarias and Pomerance, Product-free sets with high density 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:
Kurlberg, Lagarias and Pomerance, On sets of integers which are both sum-free and product-free (arXiv:1201.1317) 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:
Andrew Treglow's talk On sum-free and solution-free sets of integers cites the following result of Deshouillers, Freiman, Só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 of Kurlberg, Lagarias and Pomerance, Product-free sets with high density 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 10 hours ago
David Richerby
2,18011324
2,18011324
answered yesterday
alphacapturealphacapture
2,165425
2,165425
add a comment |
add a comment |
$begingroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
add a comment |
$begingroup$
What about $S={3n-1,|,ninmathbb N}$? Its natural density is $frac13$.
$endgroup$
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
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 yesterday
José Carlos SantosJosé Carlos Santos
163k22131234
163k22131234
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
add a comment |
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
$begingroup$
Very nice! ${}$
$endgroup$
– Joseph O'Rourke
yesterday
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$
1
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
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$
1
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
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 yesterday
answered yesterday
vadim123vadim123
76.2k897191
76.2k897191
1
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
add a comment |
1
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
1
1
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
$begingroup$
I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"!
$endgroup$
– Joseph O'Rourke
yesterday
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
yesterday
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
yesterday
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
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
yesterday
3
$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
yesterday
|
show 1 more 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
yesterday
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
yesterday
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
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
yesterday
3
$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
yesterday
|
show 1 more 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 yesterday
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
yesterday
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
yesterday
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
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
yesterday
3
$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
yesterday
|
show 1 more comment
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
yesterday
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
yesterday
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
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
yesterday
3
$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
yesterday
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
yesterday
$begingroup$
This feels like it might be the max, because of the greedy property you mentioned.
$endgroup$
– Joseph O'Rourke
yesterday
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
yesterday
$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
yesterday
6
6
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
$begingroup$
@Théophile Doesn't 1*3=3 violate the constraint?
$endgroup$
– alphacapture
yesterday
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
yesterday
$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
yesterday
3
3
$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
yesterday
$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
yesterday
|
show 1 more 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
yesterday
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
yesterday
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 yesterday
David RicherbyDavid Richerby
2,18011324
2,18011324
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
yesterday
add a comment |
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
yesterday
2
2
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
yesterday
$begingroup$
I especially like your last example: $2,3,7,22,155,3411,ldots$.
$endgroup$
– Joseph O'Rourke
yesterday
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-that-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
8
$begingroup$
Instead of adding a question after receiving an answer to your original question, you should ask that other question separately
$endgroup$
– Hagen von Eitzen
17 hours ago