¿Subconjunto de enteros que sólo ocupa (p-1) / 2 clases de equivalencia p mod?

Question

No estoy muy seguro de la mejor manera para preguntar esto, así que tengan paciencia conmigo: ¿alguien sabe de un subconjunto de los números enteros tales que, por alguna extraña primer p, el subconjunto sólo ocupa (p-1)/2 clases de equivalencia mod p (y lo hace de manera uniforme)?

Tomemos, por ejemplo, el subconjunto de los cuadrados. Elementales de la teoría de números muestra que ellos (como residuos cuadráticos) ocupar (p+1)/2 clases de equivalencia mod p. Pero la respuesta a la anterior es no tomar el no-residuos desde un no-residuo es una propiedad local, no una propiedad de un entero.

Es posible construir un conjunto de números enteros de un elemento en un tiempo de una manera ad hoc utilizando algunos de los miembros iniciales, un montón de CRT, y haciendo un poco de la elección arbitraria en cada paso. Pero hay una más `conocido" conjunto que tiene esta propiedad?

Answer 1

Aquí hay algo que me di cuenta - ninguna idea si ayuda:

Supongamos que $A\subset\mathbb{Z}$ tiene la propiedad de que por cada impar primera $p$ y $\phi_p:\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$, tenemos $|\phi_p(A)|=\frac{p-1}{2}$. Considerar el mapa $f_p:\mathbb{Z}/p\mathbb{Z}\rightarrow\mathbb{Z}/p\mathbb{Z}$ $f_p(x)=x^2$. Entonces $|f_p(\phi_p(A))|\leq\frac{p-1}{2}$. Puesto que hay $\frac{p+1}{2}$residuos cuadráticos mod $p$, que tenemos que por cada impar primera $p$, hay un $x_p\in\mathbb{Z}/p\mathbb{Z}$ tal que $a^2\not\equiv x_p^2\bmod p$ % todo $a\in A$(que es $\Leftrightarrow$ $a\not\equiv \pm x_p\bmod p$).

Answer 2

Véase la sección 4.3 de Helfgott y Venkatesh, "Cómo pequeños deben mala distribución de los conjuntos de ser?"

para un ejemplo de un subconjunto de [1..N] de de que el tamaño del log N con pequeñas proyecciones en Z/pZ, y en la sección 4.2 para una "conjetura" acerca de lo que tales subconjuntos podría ser como en la general. Especulan que tal conjunto puede ser muy pequeño (es decir, de tamaño N^eps) o altamente correlacionada con una "delgada", dicen, los valores de un polinomio (es decir, x^2, como en el primer caso que usted describe.)

Answer 3

No tengo una respuesta, pero una sugerencia: Considere la posibilidad de mirar el primorials + 1. Si usted comienza bastante tarde, debe haber algunas clases de equivalencia de golpe (sobre 1/log p para suficientemente grande p) hasta llegar a la primorial +1 que incluye p. También, uno haría bien en considerar factoriales o central de los coeficientes binomiales ( (2n!)/(n!)(n!) ) con un desfase constante.

Yo no lo llamo una respuesta porque no sé cómo natural de una secuencia que se quiere. Pero si esto es cursi lo suficiente como para ser votada abajo, me gustaría saber por qué.

Gerhard "Me Preguntan Sobre El Diseño Del Sistema" Paseman, 2010.01.19