Hipercubo y Hyperspheres

Question

Deje $n,k\in\mathbb{N}$. En este problema, la geometría de $\mathbb{R}^n$ es lo habitual en la geometría Euclidiana.

El entramado hipercubo $ Q(n,k)$ se define como el conjunto de $ \{1,2,...,k\}^n \subseteq\mathbb{R}^n$. Si queremos cubrir este hipercubo con el $m$ distintos $(n-1)$-dimensiones hyperspheres $S_1$, $S_2$, $\ldots$, $S_m$. Por "cubriendo $Q(n,k)$", quiero decir que $P(n,k)\subseteq \bigcup_{j=1}^m\,S_j$. What is the least possible value of $ m$?

El uso de un simple Combinatoria Nullstellensatz argumento, podemos demostrar que si $ \mu(n,k)$ es el mínimo posible de $ m$, luego $ A$ 1 + n\left\lfloor\frac{k - 1}{2}\right\rfloor \leq \mu(n,k) \leq 1 + n\left\lfloor\left(\frac{k - 1}{2}\right)^2\right\rfloor \,. $$ Sin embargo, el límite inferior no es nítida para un gran $ k$. Todo lo que sé es que el límite inferior es exacta para $ k = 1$, $ 2$, $ 3$, y $ 4$, así como al $ n = 1$, y para un caso en particular con $ n = 2$ $ k = 5$ (como se muestra en la figura adjunta más adelante). Mientras mis límites dar $5\leq \mu(2,6) \leq 13$, creo que el $\mu(2,6)=6$. Se puede verificar esto?

Alguien puede ayudar a mejorar estos límites? Tenga en cuenta que los límites también funciona si el $S_j$'s puede ser $(n-1)$-dimensiones hyperellipsoids, pero ¿cuál será el valor de la menor $m$ en este caso (que, para evitar confusiones, utilizaremos $\nu(n,k)$ para este menor $m$)? En otras palabras, también tenemos $ A$ 1 + n\left\lfloor\frac{k - 1}{2}\right\rfloor \leq \nu(n,k) \leq 1 + n\left\lfloor\left(\frac{k - 1}{2}\right)^2\right\rfloor \,. $$
Por ejemplo, $\nu(1,k)=\left\lceil\frac{k+1}{2}\right\rceil=\mu(1,k)$ todos los $k\in\mathbb{N}$$\nu(2,k)=1+2\left\lfloor\frac{k-1}{2}\right\rfloor$$k=1,2,3,4,5$. Observar que el límite inferior de $\nu(2,6)$ es también agudo (es decir, $\nu(2,6)=5$).

¿Qué sucede si el $S_j$'s puede ser cualquier degenerada $(n-1)$-dimensiones hyperconic secciones (en mi Combinatoria Nullstellensatz argumento no funciona, por lo que el límite inferior de la que he obtenido no tiene)? (Por no degenerada, me refiero a que cada una de las $(n-1)$-dimensiones hyperconic sección no debe ser una unión de hyperplanes de dimensiones en la mayoría de las $n-1$.) En esto, la mayoría de forma general, podemos utilizar la notación $\rho(n,k)$ para el más pequeño de $m$. El único obligado por $\rho(n,k)$ es $$ \rho(n,k) \leq 1 + n\left\lfloor\left(\frac{k - 1}{2}\right)^2\right\rfloor \,. $$ Por ejemplo, $\rho(1,k)=\left\lceil\frac{k+1}{2}\right\rceil=\mu(1,k)$ todos los $k\in\mathbb{N}$. Sin embargo, $\mu$, $\nu$, y $\rho$ no siempre coinciden. Los valores conocidos se $\rho(2,1)=1=\rho(2,2)$$\rho(2,3)=2<\mu(2,3)$, mientras que nosotros tenemos $\rho(2,4)\leq 3=\mu(2,4)$, $\rho(2,5)\leq 4 <\mu(2,5)$, y $\rho(2,6)\leq 5\leq\mu(2,6)$.

Answer 1

Aquí el resultado de $n=2$.

Como se ha discutido en los Límites para el tamaño de un círculo con un número fijo de entero puntos, un círculo de radio $R$ centrada en el origen que pasa en la mayoría de los $4(2\log_5R+1)$ entero entramado de puntos.

Nuestros círculos no necesita estar centrada en el origen, pero podemos obtener una cota superior para el denominador de la racionalidad de las coordenadas de sus centros. Suponer que al menos tres entero entramado de puntos de $(x_i,y_i)$ mentira en un círculo centrado en $(X,Y)$. Luego de restar el círculo de tres ecuaciones rendimientos

$$ x_1^2-x_2^2+y_1^2-y_2^2=2X(x_1-x_2)+2Y(y_1-y_2)\;,\\ x_1^2-x_3^2+y_1^2-y_3^2=2X(x_1-x_3)+2Y(y_1-y_3)\;. $$

Este es un sistema lineal de ecuaciones para $X$, $Y$ con coeficientes enteros, y el denominador de la solución está en la mayoría de los $2$ multiplicado por el factor determinante

$$ \left|\begin{matrix}x_1-x_2&y_1-y_2\\x_1-x_3&y_1-y_3\end{de la matriz}\right|\;. $$

(No $4$ veces debido a un factor de $2$ es también de los factores determinantes en el numerador.) Esta es el área de un paralelogramo generado por los tres puntos, que pueden ser en la mayoría de las $(k-1)^2\lt k^2$, por lo que el denominador es en la mayoría de las $2k^2$. Podemos subdividir la red por el denominador; todo el entramado puntos todavía será celosía puntos, y el radio de un círculo de radio $r$ en términos de la nueva cuadrícula constante será en la mayoría de las $R=2k^2r$. Así un círculo de radio $r$ puede pasar a través de en la mayoría de las $4(2\log_5(2k^2r)+1)$ celosía puntos.

Ahora tenemos la necesidad de acotar el radio de $r$. De nuevo suponer que al menos tres de celosía puntos de $(x_i,y_i)$ mienten en el círculo. A continuación, el área de un paralelogramo se span es un entero positivo, y por lo tanto a menos $1$. Ya que la distancia entre dos de ellos es en la mayoría de las $\sqrt2(k-1)$, para la altura de la tercera por encima de la línea de conexión debe ser al menos $1/(\sqrt2(k-1))$. Por lo menos uno de los puntos, esta altura se cruza con el lado opuesto. Luego de altitud dada, el radio del círculo es máxima si el punto es simétricamente colocados entre los otros dos puntos. Esta máxima de la radio es el radio del círculo que pasa a través de $(\pm (k-1)\,/\sqrt2,0)$$(0,1/(\sqrt2(k-1)))$, que es

$$ r_\text{max}=\sqrt{\frac{(k-1)^2}2+\frac{\left((k-1)^4-1\right)^2}{8(k-1)^2}}\le2^{-3/2}k^3\;. $$

Conectando en el obligado derivados por encima de los rendimientos

$$ \mu(2,k)\ge\frac{k^2}{4\left(2\log_5(2^{-1/2}k^5)+1\right)}\sim\frac{\log5}{40}\frac{k^2}{\log k}\approx\frac1{25}\frac{k^2}{\log k}\;. $$

Esta mejora en el lineal obligado para $k\ge122$.

Esto probablemente podría ser mejorado por un análisis más profundo, ya que los círculos de radio $k^3$ están muy cerca de una línea que pasa a través de la red; por lo menos el factor de $4$ puede asintóticamente ser sustituido por $2$, ya que en la mayoría de los $2$ el cuadrante de un círculo tan grande puede intersectar la red.

---

He quitado algunos optimistas comentarios acerca de generalizar esto para mayor $n$. Mientras que el argumento para el denominador se generaliza y los rendimientos de $R\le2k^nr$, y creo que el argumento para la máxima radio también debe generalizar y de nuevo el rendimiento de un obligado de la orden de $k^3$, lo que falta para convertir esto en un mejoramiento de los límites para el problema actual es logarítmica límite en el número de entramado de puntos en un hypersphere. De hecho, el MathWorld artículo sobre la suma de cuadrados de la función da las identidades que implican que dichos dependientes no tienen para muchos $n$.

Aquí, en caso de que alguien pueda hacer uso de ellas, son algunos de los resultados que se encuentran en la literatura. Este papel (para $n=3$) y este papel (para $n\ge4$) dan los límites de la diferencia de $\Delta_n(R)$ entre el número de celosía de puntos dentro de un $(n-1)$-esfera de radio $R$ y su volumen:

$$ \begin{align} \Delta_n(R)\in O\left(R^\theta\right)\quad\text{with}\quad\theta= \begin{cases} \frac{21}{16}+\epsilon&n=3\\ 2+\epsilon&n=4\\ n-2&n\ge5 \end{casos} \end{align} $$

Dado que el número de celosía de puntos en la esfera de salta por el número de celosía puntos sobre la esfera, ésta debe satisfacer los mismos límites.