The Number of Short Vectors in a Lattice

2011-07-23T06:11:09Z

Given a lattice $L = \bigoplus_{i=1}^{m} \mathbb{Z}v_i$ (the $v_i$ are linearly independent vectors in $\mathbb{R}^n$) and a number $c > 0$, can one quickly compute or find a good estimate on the number of lattice vectors $v$ with $|v| \leq c$ without actually enumerating these vectors? The basis $v_1,\ldots, v_m$ of the lattice can be assumed to be LLL reduced.

Also asked at: http://cstheory.stackexchange.com/questions/7488/the-number-of-short-vectors-in-a-lattice

Relating $p$-adic Valuations of Elements in $\mathbb{C}$ and $\mathbb{C}_p$

2011-07-03T21:23:26Z

Let $K = \mathbb{Q}(\theta)$, where $\theta$ is a root of an irreducible polynomial $g \in \mathbb{Z}[t]$. Fix a rational prime $p$. Let $\theta^{(1)}, \ldots, \theta^{(n)}$ be the roots of $g$ in $\overline{\mathbb{Q}}$, and let $\phi^{(1)}, \ldots, \phi^{(n)}$ be the roots of $g$ in $\overline{\mathbb{Q}_p}$ (the algebraic closure of $\mathbb{Q}_p$). Let $f \in \mathbb{Z}[t]$, and put $$ \alpha = \frac{f(\theta^{(a)})}{f(\theta^{(b)})}, \qquad \beta = \frac{f(\phi^{(c)})}{f(\phi^{(d)})}. $$ Let $L$ be a finite extension of $K$ containing $\alpha$, and let $\mathfrak{p}$ be a prime ideal of $L$ above $p$.

If $\text{ord}_p(\beta) = 0$ , is $\text{ord}_{\mathfrak{p}}(\alpha) = 0$ also? Why? What is the general relationship between $\text{ord}_p(\beta)$ and $\text{ord}_{\mathfrak{p}}(\alpha)$ ?

I know that if $\mathfrak{p}$ stands for a prime ideal of $K$ above $p$, if $g_{\mathfrak{p}}$ is the irreducible factor of $g$ in $\mathbb{Q}_p[t]$ which corresponds to $\mathfrak{p}$, and if $\phi^{(\cdot)}$ is any root of $g_{\mathfrak{p}}$, then for any $x \in K$ $$ \frac{1}{e}\text{ord}_{\mathfrak{p}}(x) = \text{ord}_p(\sigma(x)), $$ where $e$ is the ramification index of $\mathfrak{p}$ over $p$ and $\sigma$ is the embedding of $K$ into $\mathbb{Q}_p(\phi^{(\cdot)})$ that maps $\theta$ to $\phi^{(\cdot)}$ and fixes $\mathbb{Q}$ pointwise.

I have a feeling that I can view $\beta$ as the image of $\alpha$ under some embedding (there is an obvious candidate) and get a similar formula relating $\text{ord}_p(\beta)$ and $\text{ord}_{\mathfrak{p}}(\alpha)$ , but I am having trouble proving this or making it concrete.

Can someone please help?

User oshe - MathOverflow

The Number of Short Vectors in a Lattice

Relating $p$-adic Valuations of Elements in $\mathbb{C}$ and $\mathbb{C}_p$