# Sets that are both Sum-free and Product-free

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

• Instead of adding a question after receiving an answer to your original question, you should ask that other question separately – Hagen von Eitzen Feb 22 '19 at 9:51

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

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

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

• Very nice! ${}$ – Joseph O'Rourke Feb 21 '19 at 20:53

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.

• I am glad to know the terms "sum-free" and "product-free." Much more memorable than "property $Q$"! – Joseph O'Rourke Feb 22 '19 at 0:16

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 feels like it might be the max, because of the greedy property you mentioned. – Joseph O'Rourke Feb 21 '19 at 20:53
• @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. – Théophile Feb 21 '19 at 21:22
• @Théophile Doesn't 1*3=3 violate the constraint? – alphacapture Feb 21 '19 at 22:04
• @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 – alphacapture Feb 21 '19 at 22:33
• @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.) – Barry Cipra Feb 22 '19 at 0:21

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

• I especially like your last example: $2,3,7,22,155,3411,\ldots$. – Joseph O'Rourke Feb 22 '19 at 1:02