Vrftsjtryk

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}$.

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

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.

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.

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.

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:

1. $lvert Srvertle2n/5+1$


2. 
   $S$ consists of odds


3. 
   $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}$.

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}$.