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

$\endgroup$
  • 16
    $\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 Feb 22 at 9:51
23
$\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 $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}$.

$\endgroup$
34
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ Very nice! ${}$ $\endgroup$ – Joseph O'Rourke Feb 21 at 20:53
14
$\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}/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.

$\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 Feb 22 at 0:16
10
$\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 Feb 21 at 20:53
  • 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 Feb 21 at 21:22
  • 6
    $\begingroup$ @Théophile Doesn't 1*3=3 violate the constraint? $\endgroup$ – alphacapture Feb 21 at 22:04
  • 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 Feb 21 at 22:33
  • 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 Feb 22 at 0:21
4
$\begingroup$

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

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

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.