Ordenar subconjuntos del grupo cíclico para dar sumas parciales distintas

Question

Suponga que se dan una serie $S$ de % de $k$ cero los elementos de $\mathbb{Z}_n$. Siempre es posible ordenar los elementos de $S$, decir $a_1,a_2,\dots,a_k$ de tal manera que las sumas parciales $a_1,a_1+a_2,a_1+a_2+a_3,\dots,a_1+a_2+\cdots+a_k$ son todos distintos. Equivalentemente, que desea evitar pistas $a_i+a_{i+1}+\cdots+a_j$ que añadir a cero (donde $1<i<j\le k$).

En el caso de $k=n-1$ a esto se le conoce, es cubierto por la teoría de la sequenceable y $R$-sequenceable grupos. Alguien ha visto en la anterior generalización antes? Aunque $k=n-1$ se siente como lo que debería ser el más difícil caso, no parece implicar el resto de los casos. Tengo la esperanza de que una prueba para el caso de al $n$ es primo, pero antes de que me vaya para el esfuerzo de separar los detalles quiero estar seguro de que estoy no hay que reinventar la rueda.

Es tentador pensar que el problema va a ser fácil al $k$ es mucho menor que $n$. Sin embargo, es posible que $S$ podría ser distinto de cero elementos de algunos de los subgrupos de $\mathbb{Z}_n$, en el que caso de que usted simplemente está buscando una secuenciación de ese subgrupo. Esto existe, pero es muy probable que muy rara en algún sentido.

Este problema me lo contó Jeff Dinitz, y creo que él podría haberlo comprado desde Dan Arcediano. Los punteros a la literatura relevante será muy apreciada.

Answer 1

Esta no es una solución completa, pero creo que puede ser completado con un poco más de esfuerzo para el caso de que $n$ es primo. (Como usted ha señalado, para $n$ compuesto se puede ejecutar en problemas con los subgrupos, y no está claro si la afirmación es cierta en este caso.)

Suponiendo, pues, que $n$ es primo, vamos $$ P(x_1,\ldots, x_k):= \prod_{1<i<j\le k} (x_i+\dotsb+x_j) \cdot \prod_{1\le i<j\le k} (x_j-x_i) \in {\mathbb F}_n[x_1,\ldots x_k]. $$ Este es un polinomio en $k$ variables de grado $(k-1)^2$; es homogénea, por lo que ninguno de sus monomials está dominado por cualquier otro monomio.

La observación crucial es que si un conjunto $S\subset{\mathbb F}_n^\times$ no se pueden ordenar de la manera que desea, a continuación, $P$ se desvanece en el producto cartesiano $S^k=S\times\dotsb\times S$. En consecuencia, por la "generalizada Combinatoria Nullstellnsatz" (Teorema 2 de este documento por Michal Lason), $P$ no contiene ningún monomio $ax_1^{d_1}...x_k^{d_k}$ con $d_1,\dotsc,d_k<k$. En otras palabras, si podemos demostrar que $P$ contiene un monomio con el individuo grado en cada una de las variables más pequeño que $k$, entonces hemos terminado.

Jugando con pequeños valores de $k$ sugiere que $P$ contiene en realidad muchas de tales monomials; por ejemplo, $x_1^{k-1}\ldots x_{k-1}^{k-1}$ ha coeficiente de $\pm 1$ en $P$ para $k\le 5$. Me gustaría especular que los coeficientes de $P$ puede ser calculada de forma explícita, y esto debería dar el resultado.

Answer 2

Sólo un largo comentario: me pregunto si mucho más, es cierto. Por ejemplo, si $G$ es un (aditivo) abelian grupo, y $a_1,a_2,\ldots, a_k$ es una lista de no-cero, los elementos distintos de $G$ con $$(\ast)\qquad a_1+a_2+\cdots+a_k\neq 0$$ es cierto que podemos ordenar la lista por lo que $$a_i+a_{i+1}+\cdots + a_j\neq 0\text{ for all }1\leq i\leq j\leq k?$$

(He comprobado que para valores pequeños de $k$.)

Aquí está la prueba de que $(\mathbb{R},+)$ tiene esta propiedad. En primer lugar, podemos escribir la lista como $n_s<n_{s-1}<\ldots<n_1<0<p_1<p_2<\ldots<p_t$. (El $n$'s son los términos negativos, y el $p$'s son positivas.) La idea es que debemos tener en este orden y, a continuación, modificar en pequeñas maneras, para, finalmente, acabar con un orden que tiene la propiedad deseada.

Supongamos que existe un subsum que es cero. Esto significaría $\sum_{i=1}^{t_0}p_i=-\sum_{i=1}^{s_0}n_i$ para algunos $s_0\leq s,t_0\leq t$. Tomamos $t_0$ mínima con esta propiedad. (A continuación, $s_0$ es mínima así.)

Caso 1: $t_0=t$. A continuación, $s_0<s$ (por $(\ast)$), y se puede cambiar de $n_{s_0}$ e $n_{s_0+1}$ y hemos terminado.

Caso 2: $t_0<t$ e $s_0=s$. Similares.

Caso 3: $s_0<s$, $t_0<t$, y $-\sum_{i=1}^{s}n_i<\sum_{i=1}^{t_0+1}p_i$. Interruptor de $n_{s_0}$ e $n_{s_0+1}$, y de nuevo tenemos que hacer.

Caso 4: $s_0<s$, $t_0<t$, y $-\sum_{i=1}^{s}n_i\geq \sum_{i=1}^{t_0+1}p_i$. Interruptor de $p_{t_0}$ e $p_{t_0+1}$. Hay dos subcases aquí. En primer lugar, puede ocurrir que los $p_{t_0+1}+\sum_{i=1}^{t_0-1}p_i=-\sum_{i=1}^{s_1}n_i$ para algunos $s_1>s_0$. En el caso del que nos interruptor de $n_{s_1}$ e $n_{s_1+1}$. Si que subcase no sucede, entonces no nos hacen ningún interruptor adicional.

Tenga en cuenta que el único caso que no inmediatamente acabado el problema es del Caso 4. Sin embargo, después de que el interruptor(es) en el Caso 4, y luego, después de la numeración, la minimización de la $s_0$ e $t_0$ han aumentado. La otra propiedad de nuestro ordenamiento que tenemos que preservar, por lo que se puede iterar este proceso, es que los nuevos términos $p_{t'}$ e $p_{t'+1}$ vamos a cambiar (respectivamente $n_{s'}$ e $n_{s'+1}$) son estrictamente creciente (resp. disminuyendo). Rápidamente se comprueba que el Caso 4 no conserva este hecho, dado que el primer pedido.

Answer 3

Me llegó de forma independiente con una prueba en el caso real de que es un poco diferente de Ritmo del:

Vamos a resolver el problema por $\mathbb R$. Si el orden de los elementos con todos el positivo y el negativo, el pasado, sólo se pierde si algún segmento final de los aspectos positivos de los saldos de algunas segmento inicial de los negativos. Usted puede evitar esto mediante la creación de la orden en el interior con un algoritmo voraz.

Usted tiene un montón de negativos y un montón de positivos. Usted tiene una secuencia actual. Si el total es negativo, se debe agregar un positivo a la izquierda. Si el total es positivo, se debe agregar un negativo a la derecha. Mientras que el total nunca llega a cero, usted gana.

Si usted tiene más de una opción para lo que hay que añadir, siempre se puede añadir en forma tal que el total no es igual a cero. Sólo se puede perder si no es exactamente un número a la izquierda en uno de los lados, y que llegaría a un equilibrio perfecto entre la suma. Si el número es positivo, usted está en realidad muy bien - porque $a_1$ contribuye a cada suma, contribuye a ninguna de las diferencias, y de manera equilibrada suma no cuenta en realidad. A continuación, añadir todos los negativos, nunca tendrá otra equilibrado suma. Si es negativo, simplemente se invierte el orden y uso el mismo argumento.

El problema es solucionable más de $\mathbb R$, por tanto, con el $\mathbb Z$. Un fracaso para resolver el problema para un determinado $k$ puede ser visto como una solución no trivial para un determinado conjunto de ecuaciones lineales. Porque no hay soluciones más $\mathbb Z$, que no hay soluciones mod $p$ para $p$ lo suficientemente grande, por lo tanto no hay soluciones mod $n$ mientras todos los primos divisores de $n$ son suficientemente grande en relación a $k$. Creo que la mayor que $k^{k/2}$ es suficiente.