Define cada una de sus preguntas como puntos en una agenda.

Question

Imagina un n-simplex, el conjunto solución para la expresión: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, donde:

1. $a_1$ a través de $a_n$ son positivas delimitada enteros
2. $x_1$ a través de $x_n$ son positivas acotado de números reales
3. 'S' es la suma de la expresión

Este n-simplex, por tanto, tiene un vértice en el origen, así como un vértice en cada uno de los ejes en algunos arbitraria (estrictamente positivo) distancia desde el origen.

¿Cuál es el entramado entero, en punto de cuenta?

Se puede utilizar Ehrhardt polinomios para calcular el entero conteo de puntos para el n-simplex, tal vez bajo la restricción de que hemos vértices estrictamente en coordenadas enteras?

• Desde "la Geometría de N Dimensiones Gráficos" (por Andrew J. Hanson, CS Dept., Universidad de Indiana), sabemos que las orientadas volumen de la n-simplex con vértices {$v_1$, ..., $v_n$}, o {$a_1$*$x_1$, ..., $a_n$*$x_n$} es:

$V_n$ = $\dfrac{1}{n!}$ * det([($v_1$-$v_0$), ..., ($v_n$-$v_0$)])

(Los problemas de la escritura de Látex para matrices de aquí, por favor consulte los términos como vectores columna para obtener la matriz cuadrada.)

---

Anterior a la formulación de la pregunta: Imagina una expresión de la forma: $a_1$*$x_1$ + $a_2$*$x_2$ + ... + $a_n$*$x_n$ = S, donde:

1. $a_1$ a través de $a_n$ son positivas delimitada enteros
2. $x_1$ a través de $x_n$ son positivas acotado de números reales
3. 'S' es la suma de la expresión

Podemos decir nada sobre el máximo valor de " S " (para un determinado $x_1$ a través de $x_n$) por debajo de la cual sólo hay una solución para el entero positivo coeficientes de $a_1$ a través de $a_n$? Por ejemplo, dada la expresión $a_1$*98 + $a_2$*99 = 'S', donde los coeficientes de $a_1$ $a_2$ = [1 a 100], se encuentra que siempre se puede exactamente recuperar el original $a_1$ $a_2$ si 'S' < 9899. Hay una analítica o más elegante método para la obtención de los que se unía?

[Por encima de estas obligado, es allí una manera eficiente para obtener todos los posibles conjuntos de números enteros $a_1$ a través de $a_n$ que satisfacen la relación de un determinado 'S'? Puede la liga de la leche o PSLQ algoritmos?] <-- Esto parece ser una restringido/caso especial de que el subconjunto de suma problema, por lo que los algoritmos de programación dinámica. Se puede hacer mejor aquí?

Answer 1

A partir de la descripción del problema, supongo que el $x_i$ a partir de los dos primeros párrafos son lo que se llama $r_i$ más tarde. Yo todavía no tiene una respuesta completa, pero quisiera señalar algunas observaciones y las ideas (lo siento, no puedo escribir comentarios todavía):

A mí me parece que podemos, sin pérdida de generalidad, supongamos la $x_i$ a ser conmensurables. De lo contrario, split $S\in\mathbb{Z}[x_1,\dots,x_n]$ en una representación wrt una base de $\mathbb{Z}[x_1,\dots,x_n]$.

Por lo tanto, al multiplicar a través de un adecuado constante, podemos asumir que el $x_i$ son enteros positivos. También podemos asumir $\gcd(x_1,\dots,x_n)=1$, ya que de lo contrario, cualquier $S$ para que la ecuación tiene una solución también es divisible por esta dpc, que permite dividir la ecuación. Edit: estos dos supuestos simplificadores cambio el conjunto de soluciones (soluciones para algunos otros $S$$r_1,\dots,r_n$, pero en un bijective manera.

El número de soluciones para cualquier particular $S$ $x_1,\dots,x_n$ puede ser contado el uso de funciones de generación (similar a Polya del método para el recuento de posibilidades de dar el cambio); con su ejemplo,$S=98\,a_1+99\,a_2$$0 \leq a_1,a_2 \leq 100$, el número de soluciones para $S$ es el coeficiente de $x^S$ en el polinomio $(x^{98}+x^{2\cdot98}+\cdots+x^{100\cdot98})\,(x^{99}+x^{2\cdot99}+\cdots+x^{100\cdot99})$, cuya menor exponente con el coeficiente más grande que la de $1$$9899$.

---

No estoy seguro de que tengo una buena forma de explicar esto. Esencialmente, el primero de estos polinomios es la generación de la función para el número de soluciones para $S=98\,a_1$ y la segunda es la generación de la función para el número de soluciones para $S=99\,a_2$. Dado que en estas funciones de generación, el $S$ valores de los exponentes, que la suma de los $S$ valores corresponde a la multiplicación.

Si quieres escribir un programa de computadora para encontrar el más pequeño de $S$ de manera tal que el coeficiente correspondiente en la generación de la función como se indica más arriba cumple alguna condición (por ejemplo, es mayor que $1$), probablemente sería una buena idea utilizar el estándar escrito de la multiplicación y la uso un montón de estructura para llevar a cabo los pasos. Dicha aplicación podría proporcionar un flujo de coeficiente/exponente pares y también se puede utilizar como uno de sus dos entradas, lo que significa que la multiplicación de muchos polinomios se puede realizar con poca sobrecarga de memoria, sobre todo, sin necesidad de almacenar todos los coeficientes ya comprobado y se determinó que no interesantes, y el cálculo puede dejar casi sin la computación nada más allá de la primera "interesante" plazo.

Answer 2

Para un polinomio de tiempo método de conteo de número entero entramado de puntos para el n-simplex (con dimensión fija):

Artículo de revisión - Crites, R., Goff, M., Korson, M., Patrolia, L., Wolcott, L. "el Recuento de Celosía Puntos en los Poliedros."

Disponible aquí con referencias para Barvinok 1994 y 1999 algoritmos - http://www.math.washington.edu/~thomas/docencia/m583_s2008_web/Barvinok.pdf

Para una aplicación de Barvinok del algoritmo, véase J. A. De Loera del LattE programa (alojado en la UC Davis): http://www.math.ucdavis.edu/~latte/group.htm

Answer 3

Estoy informado de que usted está "contando entramado de puntos dentro de un poliedro."

Aquí está una conferencia sobre el tema - la imagen en la página seis se parece a la versión del problema que usted está interesado en. Para ser honesto, me he encontrado con estas notas, haciendo una búsqueda en google. Me han dicho que este es un campo enorme!

Puede ayudar si usted puede limitar su problema aún más. Por ejemplo, decir que el $x_i$ son acotados de números reales. ¿Sabes que estas a algunos de alta precisión? O se puede dar un poco de información sobre cómo el $x_i$ se dan? Y se puede decir lo mismo de $S$?

EDITAR: Aquí está una encuesta en papel por el mismo autor, Jesús De Loera, que cubre el mismo material en mayor detalle.