¿Cuántos productos diferentes se pueden formar multiplicando $n$ números en más de una vez?

Question

Deje $a_1,\dots a_n$ ser distinto de cero de los números complejos. Productos en los que cada uno aparezca en más de una vez (incluyendo $1$ "vacío producto") será $$1,\ a_1,\ a_2,\dots a_n,\ a_1a_2,\ a_1a_3,\dots, a_{n-1}a_n,\dots, a_1a_2\dots a_n\,;$$ para el total de $2^n$ (número de subconjuntos formados a partir de $n$ elementos). Por supuesto, dependiendo del $a_i$, no todos los productos pueden ser distintas, por ejemplo, si $a_1=a_2=\dots =a_n=a$ solo $n+1$ productos distintos: $$1,\ a,\ a^2,\dots,a^n.$$ Esto puede ser reducido aún más por el supuesto de que $a^m=1$ algunos $m\leq n$, e $a=1$ reduce el número de a $1$. Hacer todos los $a_i$ igual no es la única manera de conseguir $n+1$, teniendo en $a_2=a_1^{-1}$ también lo hace por $n=2$, dicen.

Pregunta: parece que si ninguno de $a_i$ es una raíz de la unidad, a continuación, $n+1$ es el número más bajo. ¿Cómo hace uno para demostrar que? Es la cuestión de que los números entre el $n+1$ $2^n$ son realizables para algunos $a_i$ estudió? Donde puedo leer sobre esto?

La pregunta es de interés en el estudio de los productos de $u_k=\prod_{i=1}^n(1-a_i^k)$, que representan el llamado de divisibilidad entre secuencias. La apertura de la rotación de producto en una suma de poderes con los coeficientes, y el número de los distintos poderes es el número que se discutieron anteriormente. Se dará a la recurrencia de la orden de la divisibilidad de la secuencia.

Answer 1

$2$ pruebas de seguir, uno sobre el número mínimo deseado de los productos, de los otros con respecto a los números que no aparecen como el número de productos.

Prueba 1: Una alternativa a prueba a través de un algoritmo.

Revisión de los números de $a_1, \ldots, a_n$ que no son raíces de la unidad, ni $0$. Llame a $C$ el conjunto de productos que hemos considerado. Lugar $1$$C$, entonces para cada a $i$:

Si $a_i \not \in C$: agregar$a_i$$C$.

Otra cosa: existe alguna máximo entero positivo $k$ tal que $a_i^k \in C$, añada $a_i \cdot a_i^k$$C$.

Volver

Los elementos de $C$ siempre son distintas, como $a_i$ es sólo añadir, si es nueva, y la $a_i^{k+1}$ no puede ser en $C$, ya que implicaría hemos escogido $k$ demasiado pequeño! (esto también utiliza el hecho de que $a_i$ no son las raíces de la unidad ni $0$, por lo tanto $a_i^k$ son todos distintos. Un argumento a través de su magnitud o el ángulo en el plano complejo es suficiente)

Nota al final del algoritmo, $|C| = n+1$, independientemente de $a_i$ (siempre y cuando cumplan las condiciones de base). Esto es debido a que sólo agregar nuevos elementos a $C$ desde $a_i$ (que no ha sido previamente considerado) o $a_i$ veces un elemento ya en $C$ (que debe haber sido formado a partir de $a_j$$j < i$).

Por supuesto, uno podría añadir más elementos a $C$ y obtener toda la lista deseada de esta manera, pero el de arriba siempre va a existir en un mínimo.

Prueba 2: con Respecto al estudio de los números que no aparecen como el número de productos de $n$ números - no hay triviales tales valores. Cada valor de $v$ $1$ $2^n$ tiene un conjunto de $n$ enteros positivos $a_i$ tal de que no se $v$ valores distintos que puede estar formado por productos de las $a_i$ (cada utilizado en más de una vez). Voy a usar la notación $a(m,k,i)$ para denotar el valor de $a_i$, de modo que no se $m$ productos de uso $k$ enteros. La prueba procede por inducción.

En primer lugar, la afirmación es fácil de comprobar cuando se $n=1$, ya que entonces, las asignaciones $1$ $2$ satisfacer.

Ahora supongamos que para la inducción de la afirmación es verdadera para $n=k-1$. Nótese que esto implica que $a(m,k-1,i)$ existen y pueden ser bien definidos para $m \in [1, 2^{k-1}]$. Sabemos que todos los valores en el intervalo de $[1, 2^{k-1}]$ se puede lograr mediante el establecimiento $a_k = 1$ y el uso de $a_i = a(m, k-1, i)$ para el resto de los valores.

Consideramos que el resto de los valores en $2$ categorías, pares e impares. Podemos conseguir cualquier número $2m \leq 2^k$ mediante el establecimiento $a_i = a(m, k-1, i)$, y luego seleccionando $a_k$ principal más grande que cualquiera de las $a_i$ (o cualquier número relativamente primos a los otros - no importa cómo lo tomamos). Desde $gcd(a_k, a_i) = 1$, $a_k \cdot p$ cualquier $p$ un producto de la $a_i$ es nuevo.

Para cualquier número impar $2m-1 < 2^n$ (y mayor que $1$), sólo tenemos que recoger $a_i = a(m,k-1,i)$ y $$a_k = \max_{S \subset [k-1]} \prod_{i \in S} a_i,$$ in words: the largest number we could form from the first $k-1$ $a_i$. Note because our odd number is greater than $1$, $a_k \neq 1$. Therefore for all products $p$ $a_k \cdot p \geq a_k$, so all products that involve $a_k$ are new values, and since $a_k \cdot p = a_k \cdot p' \iff p = p'$, each of these is unique. Therefore we have $2m$ possible products ($p$ and $a_k \cdot p$), minus one as $a_k = \max_{S \subconjunto [k-1]} \prod_{i \in S} a_i$ ya es un posible producto.

El caso de $1$ es trivial, acaba de establecer todos los $a_i = 1$.

Así, cada número entre el $1$ $2^n$ es de un tamaño posible para el conjunto de los distintos productos. Esto se puede generalizar para todos los números entre $n+1$ $2^n$ sin el uso de $1$'s a través de darse cuenta de que los adicionales de la base de casos $v = n+i$, todo puede ser realizado usando$a_i = 2$$i < n$,$a_n = 2^i$, y el uso de la misma inducción (que ahora ya no tendrá ninguna $a_i$$1$'.

Answer 2

Deje $\mathcal{P}:=\big\{\prod_{i\in S}\,a_i\,|\,S\subseteq\{1,2,\ldots,n\}\big\}$. Pretendemos que, si ninguna de las $a_i$s'es cero o una raíz primitiva de la unidad, a continuación,$|\mathcal{P}|\geq n+1$. Vamos que en lugar de demostrar una declaración más fuerte que $|\mathcal{P}|\geq n+1$ y la igualdad ocurre si y sólo si existe $a\neq 0$ tal que $a_i\in\left\{a,\frac{1}{a}\right\}$ por cada $i=1,2,\ldots,n$.

La prueba se hace por inducción sobre $n$. La base de casos $n=1$ $n=2$ son triviales. Ahora supongamos por el contrario que la reclamación $|\mathcal{P}|\geq n+1$ falla para algún entero positivo $n>2$. Mediante la eliminación de $a_n$ de la lista, se obtiene el conjunto de $\mathcal{P}'$ de los productos que involucran sólo a $a_1,a_2,\ldots,a_{n-1}$. Por hipótesis de inducción, $|\mathcal{P}'|\geq n$. Desde $|\mathcal{P}|<n+1$, llegamos a la conclusión de que $|\mathcal{P}|=n$, lo $\mathcal{P}=\mathcal{P}'$. Por hipótesis de inducción, existe $a\in\mathbb{C}\setminus\{0\}$ tal que $a_i\in\left\{a,\frac{1}{a}\right\}$ todos los $i=1,2,\ldots,n-1$. Por tanto, para algunos entero$m$$0\leq m\leq n$, tenemos $$\mathcal{P}'=\left\{\frac{1}{a^m},\frac{1}{a^{m-1}},\ldots,a^{n-2-j},a^{n-1-m}\right\}\,.$$ Desde $a_n\mathcal{P}'\subseteq\mathcal{P}=\mathcal{P}'$, $a_n=a^k$ para algunos $k\in\{-m,-m+1,\ldots,n-2-m,n-1-m\}=:T$. Desde $a_n$ no es una raíz primitiva de la unidad, $k\neq0$.

Si $k>0$,$a_na^{n-1-m}=a^{n-1-m+k}\in\mathcal{P}'$, lo $a_na^{n-1-m+k}=a^j$ algunos $j\in T$. Es decir, $a^{n-1-m+k-j}=1$. Tenemos $$n-1-m+k-j\geq n-m-j\geq 1\,.$$ Therefore, $un$ is a primitive root of unity, which is absurd. Thus, $|\mathcal{P}|\geq n+1$ must hold. On the other hand, if $k<0$, then $a_na^{m}=a^l$ for some $l\T$. That is, $^{l+m-k}=1$. Tenemos $$l+m-k\geq l+m+1\geq 1\,.$$ Ergo, $a$ es de nuevo una raíz primitiva de la unidad, lo cual es una contradicción.

Ahora, supongamos que el $|\mathcal{P}|=n+1$. Consideremos el conjunto a $\mathcal{P}'$ como antes. Si $\left|\mathcal{P}'\right|=n+1$,$\mathcal{P}'=\mathcal{P}$$a_n\mathcal{P}'=\mathcal{P}'$. Es decir, $\mathcal{P}'$ es una progresión geométrica con razón común $a_n$, pero, a continuación, $a_n^{n+1}=1$ debe sostener, lo cual viola el requisito de que $a_n$ no ser una raíz primitiva de la unidad. Por lo tanto, $\left|\mathcal{P}'\right|=n$ deben tener. Sin embargo, ahora es un ejercicio fácil, usando la hipótesis de inducción, para mostrar que no existe $a\neq 0$ tal que $a_i\in\left\{a,\frac{1}{a}\right\}$ por cada $i=1,2,\ldots,n$.