5 votos

Límites superior en el Número de Celosía Puntos en un $n$-Simplex

Vamos $\Omega = $ {$\omega_{i}$} ser un conjunto ordenado de $n$ positivos reales en la unidad de intervalo, $\omega_{1} \leq \cdots \leq \omega_{n} \leq 1$. Definir el $n$-simplex $\Delta(\Omega; (\mathbb{R}^{+})^{n})$ por la falta de puntos negativos $(x_{1}, \dots, x_{n}) \subset (\mathbb{R}^{+})^{n}$ que satisfacen la desigualdad \begin{eqnarray} \omega_{1} x_{1} + \cdots + \omega_{n} x_{n} \leq 1. \end{eqnarray} Deje $X$ ser un no-trivial subconjunto de los números enteros $\mathbb{Z}^{n}$. Definir $\Delta(\Omega, X) = X \cap \Delta(\Omega, (\mathbb{R}^{+})^{n})$. Es bien conocido que \begin{eqnarray} |\Delta(\Omega, \mathbb{N}^{n})| \leq \frac{1}{n!} \prod_{i = 1}^{n} \frac{1}{\omega_{i}} \quad \text{and} \quad |\Delta(\Omega, (\mathbb{Z}^{+})^{n})| \leq \frac{1}{n!} \left(1 + \sum_{i = 1}^{n} \omega_{i} \right)^{n} \prod_{i = 1}^{n} \frac{1}{\omega_{i}}, \end{eqnarray} donde $\mathbb{Z}^{+}$ denota el conjunto de enteros no negativos.

Pregunta(s): Para los límites fijados anteriormente, son las más nítidas de los límites conocidos? Dada la similitud en la forma, hay fórmulas para otros $X$ conjuntos, dicen que para enteros mayores que algunos entero arbitrario $c$ o enteros satisfacer algunas de congruencia condición (por ejemplo, $a \equiv b$ mod $d$)?

(Actualización) La teoría de Ehrhart polinomios es relevante para la pregunta anterior.

Pregunta: Supongamos que me gustaría utilizar el Ehrhart maquinaria para contar el número de entero no negativo soluciones de $a_{1} x_{1} + \cdots + a_{n} x_{n} \leq r$ para un entero no negativo, $r$ y enteros positivos {$a_{i}$}. ¿Cómo proceder?

Gracias!

27voto

John Fouhy Puntos 759

Si $\omega_1 = \cdots = \omega_n = 1/k$, entonces la ecuación se traduce en

$\displaystyle x_1 + \cdots + x_n \leq k$

y por lo que el número de entero no negativo soluciones es $\binom{n+k-1}{k}$, que es aproximadamente el $n^k/k!$, frente a su estimación $k^n/n!$ (eso suponiendo $k$ es mucho menor; si asumimos $n$ es mucho menor, podemos obtener su estimación).

Por cierto, ¿cómo se derivan de su propio límite superior? Supongo que usted comience con el volumen de la simplex $1/n!$ y, a continuación, volar dimensión$i$$1/\omega_i$, al pasar su expresión. ¿Cómo relacionarlo con el número de celosía puntos? Usted puede construir fácilmente un convexo polytope arbitrariamente pequeña área con arbitrariamente muchos de celosía puntos.

4voto

RodeoClown Puntos 3949

En respuesta a tu pregunta sobre cómo utiliza el Ehrhart maquinaria para contar el número de celosía puntos en $a_1 x_1 + \cdots + a_n y_n \le r$ con entero $r$ $a_i$ ver estos papeles de Matt Beck en el recuento de celosía de puntos racionales simplices (y que simplex en particular.) Otros papeles de su probablemente son también relevantes. Estoy bastante seguro de que también es cubierto en el Cómputo de la Continua Discretamente (vale la pena leer, independientemente de si se contesta a tu pregunta.)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X