Conjuntos que son libres de sumas y libres de productos

Question

Deje $P_o$ ser los números primos excluyendo $2$. $P_o \subset \mathbb{N}$ tiene la siguiente propiedad $Q$:

• Para cualquier $a,b \in P_o$, $a + b \not\in P_o$.
• Para cualquier $a,b \in P_o$, $ab \not\in P_o$.

Por lo tanto la adición y la multiplicación necesariamente abandonar el conjunto $P_o$.

$P_o$ tiene natural de la densidad de $0$.

Q1. Hay una serie $S \subset \mathbb{N}$ con densidad positiva que satisface la propiedad de $Q$?

Respondió rápidamente por @JoséCarlosSantos: Sí. Me permito añadir una nueva pregunta:

Q2. ¿Cuál es la mayor densidad de $S \subset \mathbb{N}$ que satisface la propiedad de $Q$?

Santos del ejemplo tiene una densidad de $\frac{1}{3}$.

Answer 1

¿Qué pasa con $S=\{3n-1\,|\,n\in\mathbb N\}$ ? Su densidad natural es $\frac13$ .

Answer 2

Nueva respuesta:

Kurlberg, Lagarias y Pomerance, En conjuntos de números enteros que son de suma y libre de producto-libre (arXiv:1201.1317) responde a la pregunta. La parte superior de la densidad de cualquier conjunto es estrictamente menor que 1/2, pero puede ser arbitrariamente cerca de 1/2. No veo que el estado presente de manera explícita en el papel, pero que sigue muy rápido de Teorema 1.3.

Explícitamente: Teorema 1.3 implica que para cualquier $\varepsilon>0$ hay algo de $n$ y un subconjunto $S\subset\mathbb{Z}/n\mathbb{Z}$ de los residuos de las clases que se suma libres y producto libre que consta de al menos $(\frac{1}{2}-\varepsilon)n$ de las clases. Luego de tomar todos los valores enteros en los residuos de clases da un producto libre de suma-libre conjunto de números enteros de la densidad de al menos $(\frac{1}{2}-\varepsilon)$.

Respuesta anterior:

Andrew Treglow a hablar En suma-libre y solución libre de los conjuntos de números enteros cita el siguiente resultado de Deshouillers, Freiman, Sós y Temkin (1999):

Si $S\subseteq[n]$ es de suma libre, entonces al menos uno de los siguientes sostiene:

1. $\lvert S\rvert\le2n/5+1$
2. $S$ consta de probabilidades
3. $\lvert S\rvert\le\min(S)$.

Por lo tanto, si la densidad de una suma-producto libre-juego gratis $P$ de los enteros es mayor que 2/5, a continuación, $P\cap[n]$ debe caer en el segundo caso para suficientemente grande $n$. (Que no puede estar en el tercer caso, porque $\min(P)<2n/5$ para suficientemente grande $n$.)

Así, la única manera en que podemos hacerlo mejor que 2/5 es utilizar sólo números impares, y como corolario la densidad más alta que podemos esperar es 1/2.

De hecho, la prueba de la Observación 2.7 de Kurlberg, Lagarias y Pomerance, Producto libre de grupos con alta densidad se traslada para el caso de sólo números impares, mostrando que no podemos alcanzar una densidad de 1/2. La integridad, repetimos el argumento aquí con las modificaciones correspondientes: Vamos a $a$ denotar el menor elemento de a$P$, y deje $P(x):=P\cap[1,x]$. Desde $P(x)\setminus{P(x/a)}$ se encuentra en $(x/a,x]$, $\lvert P(x)\rvert\le \lvert P(x/a)\rvert+\frac{x-\lfloor x/a\rfloor}{2}+1$. También, multiplicando cada uno de los miembros de $P(x/a)$ crea productos en $[1,x]$ que no puede mentir en $P$, por lo que tenemos $\lvert P(x)\rvert\le \frac{x}{2}+1-\lvert P(x/a)\rvert$. La adición de estas dos desigualdades y dividiendo ambos lados por 2 da $\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 3

Esto no comenzó como una respuesta, pero ver a editar a continuación.

Ver esta charla por Carl Pomerance, en suma-libre de conjuntos, y el producto libre de conjuntos. Una manera de responder a la OP (y este es el enfoque de las otras respuestas) es elegir una $n$, y un subconjunto $S$ de $\mathbb{Z}/n\mathbb{Z}$, de tal manera que $S$ es tanto la suma gratuita (si $a,b\in S$, a continuación, $a+b\notin S$) y de productos (si $a,b\in S$, a continuación, $ab\notin S$) . Entonces, tomamos todos los números enteros que son congruentes a un elemento de $S$, modulo $n$. El deseado de forma asintótica de la densidad se ve $\frac{|S|}{n}$.

Esto podría no ser una simple pregunta. Teniendo en cuenta sólo la suma propiedad libre , se puede conseguir fácilmente la densidad asintótica $0.5$ tomando los números impares. El producto libre de propiedad es bastante sutil: el vinculado hablar da una construcción de un gran $n$ (con más de 100 millones de dígitos) que hay un $S$ satisfacción $\frac{|S|}{n}>0.5003$. De hecho, se podría plantear $0.5003$ ser arbitrariamente cerca de $1$ (aunque no de la construcción se da en los enlaces de hablar). El enfoque general es hacer $n$ tiene muchos primos pequeños, a los grandes poderes, como los factores.

No sería de esperar que este producto esta libre de conjunto es también de suma-libre, pero siempre podemos quitar algunos elementos de ella, hasta que un subconjunto de a$S$ que es suma-libre y producto. No tengo idea de cómo de grande que el subconjunto resultante sería.

---

EDIT: Siguiendo los métodos de la charla, elija $n$ (se supone) y producto libre de $S$, por lo que $\frac{|S|}{n}\ge 1-\epsilon$. Por lo tanto $|S|\ge n(1-\epsilon)$. $S$ contiene en la mayoría de las $\frac{n}{2}$ números (desde $S\subseteq \{0,1,\ldots, n-1\}$, la mitad de los cuales son incluso). Tome $T$ a ser el conjunto de todos los números impares en $S$. Tenemos $|T|\ge |S|-\frac{n}{2}=n(\frac{1}{2}-\epsilon)$. Desde $T\subseteq S$, $T$ es producto libre. $T$ es también de suma-libre, ya que la suma de dos elementos de la $T$ son incluso (y, por tanto, no se en $T$). La densidad asintótica de todos los productos naturales congruente a un elemento de $T$ modulo $n$ es $\frac{|T|}{n}\ge \frac{1}{2}-\epsilon$.

Tenga en cuenta que un asintótica de la densidad de $\frac{1}{2}$ es el mejor posible para la suma libre de conjuntos (como se demostró en Pomerance de diapositivas), mucho menos de suma-producto libre-libre de conjuntos. La anterior construcción da un subconjunto de a$\mathbb{N}$ arbitrariamente cerca de esta obligado.

Answer 4

Deje $S = \{n : n \equiv 2\ \rm{or}\ 3 \pmod 5\}$ . Esto tiene una densidad $2/5$ , que supera a $1/3$ .

Por cierto, esta secuencia se puede generar con un algoritmo codicioso, comenzando con $S = \{2\}$ y agregando progresivamente cada número mayor que mantiene el requisito.

Answer 5

La respuesta a la pregunta del título es no. $Q$ no caracterizar los impares, números primos, ya que, por ejemplo, $\{2,3,15\}\vDash Q$. Debido a $Q$ es el puramente universal de la propiedad $\forall x,y,z\,(x+y\neq z\land x\times y\neq z)$, cualquier subconjunto de un modelo es un modelo así, por ejemplo, cualquier subconjunto de los impares, números primos satisface $Q$. Usted puede también satisfacer $Q$ tomando el impares primos junto con cualquiera incluso integer $k$ y la eliminación de uno de cada par de números primos que difieren por $k$. O se olvidan de los números primos en conjunto y tomar cualquier finito (o infinito) set $\{a_1, a_2, \dots\}$ tal que $2\leq a_1 < a_2$ y, para todos los $i>2$, $a_i > a_{i-1}a_{i-2}$.