Sets that are both Sum-free and Product-free

Question

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 \not\in P_o$.
• For any $a,b \in P_o$, $ab \not\in 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}$.

Answer 1

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 $S\subset\mathbb{Z}/n\mathbb{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 $S\subseteq[n]$ is sum-free then at least one of the following holds:

1. $\lvert S\rvert\le2n/5+1$
2. $S$ consists of odds
3. $\lvert S\rvert\le\min(S)$.

Therefore, if the density of a sum-free product-free set $P$ of integers is greater than 2/5, then $P\cap[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):=P\cap[1,x]$. Since $P(x)\setminus{P(x/a)}$ lies in $(x/a,x]$, $\lvert P(x)\rvert\le \lvert P(x/a)\rvert+\frac{x-\lfloor x/a\rfloor}{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)\rvert\le \frac{x}{2}+1-\lvert P(x/a)\rvert$. Adding these two inequalities and dividing both sides by 2 gives $\lvert P(x)\rvert\le \frac{x}{2}-\frac{\lfloor x/a\rfloor}{2}+2$, which implies that the upper density of $P$ is at most $\frac{1}{2}-\frac{1}{2a}$.

Answer 2

What about $S=\{3n-1\,|\,n\in\mathbb N\}$? Its natural density is $\frac13$.

Answer 3

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.

Answer 4

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}/n\mathbb{Z}$, such that $S$ is both sum-free (if $a,b\in S$, then $a+b\notin S$) and product-free (if $a,b\in S$, then $ab\notin 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 $S\subseteq \{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 $T\subseteq 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.

Answer 5

The answer to the title question is no. $Q$ doesn't characterize the odd primes, since, for example, $\{2,3,15\}\vDash Q$. Because $Q$ is the purely universal property $\forall x,y,z\,(x+y\neq z\land x\times y\neq z)$, any subset of a model is a model so, for example, any subset of the odd primes satisfies $Q$. You can also satisfy $Q$ by taking the odd primes along with any 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 $2\leq a_1 < a_2$ and, for all $i>2$, $a_i > a_{i-1}a_{i-2}$.