How to Obtain Reduction Maps for n-dimensional Infrastructures.

Abstract.
We explain a general technique to obtain a reduction map, given X and d and, varying with the method of construction, additional information for every x in X. Moreover, we explain a technique on how to obtain n-dimensional infrastructures from certain lattices in (n+1)-dimensional space.

So far, we have seen how $n$ -dimensional infrastructures can be defined. In the case of one-dimensional infrastructures, we saw that there is a (more or less) obvious way how to define a reduction map, which does not extend to the $n$ -dimensional case. We next want to motivate how a reduction map can be defined given $X$ and $d$ , using additional information which might be easier to obtain.

First, introduce on $\R^n$ a lexicographic order as follows: for $a = (a_1, \dots, a_n)$ and $b = (b_1, \dots, b_n)$ , define $\displaystyle a \le b :\Longleftrightarrow \exists i \in \{ 1, \dots, n \} : a_i \le b_i \wedge \forall j < i : a_i = b_i.$ Note that this choice is rather random and can easily be replaced by other choices.

Assume that $\Lambda \subseteq \R^n$ is a lattice, $X \neq \emptyset$ a finite set and $d : X \to \R^n / \Lambda$ injective. Consider the projection $\pi : \R^n \to \R^n/\Lambda$ , $x \mapsto x + \Lambda$ and $\hat{X} := \pi^{-1}(d(X))$ . Defining a function $\psi : \R^n / \Lambda \to X$ is the same as defining a function $\varphi : \R^n \to \hat{X}$ which is invariant under $\Lambda$ , i.e. satisfies $\varphi(t + \lambda) = \varphi(t) + \lambda$ for all $\lambda \in \Lambda$ ; in that case, we can set $\psi(t + \Lambda) := d^{-1}(\varphi(t) + \Lambda)$ . Note that the condition $\psi \circ d = \id_X$ translates to $\varphi|_{\hat{X}} = \id_{\hat{X}}$ .

Hence, we have a discrete set $\hat{X} \subseteq \R^n$ which is invariant under translation by $\Lambda$ , and we want to define a function $\varphi : \R^n \to \hat{X}$ satisfying $\varphi|_{\hat{X}} = \id_{\hat{X}}$ .

Both of the two sections which follow describe one way to obtain such $\hat{X}$ and $\varphi$ . The way describes in the second section fits perfectly for all totally real number fields $K$ : think of $\Gamma$ as the image of the ring of integers $\calO_K$ under all embeddings $\sigma_1, \dots, \sigma_{n+1} : K \to \R$ , i.e. $\displaystyle \Gamma = \{ (\sigma_1(x), \dots, \sigma_{n+1}(x)) \mid x \in \calO_K \}.$ The first section resembles more the general global field situation. The set $X$ will consist of a finite set of ideals with bounded norms. The degree map will be the logarithm of the norm, and the $b_i$ ‘s correspond to the degrees of the infinite places.

Constructing a Reduction Map.

In this section, we describe a way to construct a reduction map $\varphi$ , given $\hat{X}$ .

The main idea in the following is that if we want to define $\varphi(t)$ for $t = (t_1, \dots, t_n) \in \R^n$ , to consider the area $\displaystyle B_t := \{ (x_1, \dots, x_n) \in \R^n \mid \forall i : x_i \le t_i \}$ and look at all elements $\hat{X} \cap B_t$ . By adding additional (numeric) information to every of these elements, one obtains an order (by comparing the additional information) which hopefully has a largest element, or a finite set of largest elements. From these largest elements, one chooses the largest one with respect to the lexicographic order $\le$ as $\varphi(t)$ .

To make this “additional information” more precise, we consider special functions $\deg : \hat{X} \to \R$ which should behave in a good way:

Definition.

A function $\deg : \hat{X} \to \R$ is said to be reduction-inducing if

there exist real numbers $b_1, \dots, b_n > 0$ such that, for $x \in \hat{X}$ and $\lambda = (\lambda_1, \dots, \lambda_n) \in \Lambda$ , we have $\displaystyle \deg x + \sum_{i=1}^n b_i \lambda_i = \deg (x + \lambda);$ and

for every $x = (x_1, \dots, x_n) \in \hat{X}$ , we have $Formula does not parse: \displaystyle B_x := \{ x' = (x_1′, \dots, x_n') \in \hat{X} \mid x_i' \le x_i, \; \deg x' > \deg x \} = \emptyset.$

Note that by this definition, there exist $a, A \in \R$ such that $\displaystyle a \le \deg (x_1, \dots, x_n) - \sum_{i=1}^n x_i b_i \le A$ for all $x = (x_1, \dots, x_n) \in \hat{X}$ . Moreover, note that these functions with $a, A, b_1, \dots, b_n$ fixed correspond to functions $\deg' : X \to [a, A]$ by $\displaystyle \deg (x_1, \dots, x_n) = \deg' d^{-1}((x_1, \dots, x_n) + \Lambda) + \sum_{i=1}^n x_i b_i$ for $x = (x_1, \dots, x_n) \in \hat{X}$ .

Let $\deg : \hat{X} \to \R$ be a reduction-inducing function. For $t = (t_1, \dots, t_n) \in \R^n$ and $\ell \in \R$ , consider $\displaystyle B_{t,\ell} := \{ x \in \hat{X} \cap B_t \mid \deg x \ge \ell \}.$ Note that since $\deg x \le A + \sum_{i=1}^n x_i b_i$ for $x = (x_1, \dots, x_n) \in \hat{X} \cap B_t$ , and $x_i \le t_i$ , we see that $B_{t,\ell}$ is finite for every choice of $\ell$ . If $A + \sum_{i=1}^n t_i b_i < \ell$ , we have $B_{t,\ell} = \emptyset$ , and as $X \neq \emptyset$ we get $\abs{B_{t,\ell}} \to \infty$ for $\ell \to -\infty$ . Hence, $\ell(t) := \max\{ \ell' \mid B_{t,\ell'} \neq \emptyset \}$ exists. Then, define $\varphi(t) := \max_{\le} B_{t,\ell(t)}$ .

Let $C \in \R$ be a constant such that for all $t = (t_1, \dots, t_n) \in \R^n$ , we have $\displaystyle B_{t,\ell} \neq \emptyset \quad \text{for } \ell := \sum_{i=1}^n t_i b_i + C.$ Note that since $\deg$ is reduction-inducing, a maximal such $C$ exists.

Lemma.

For $x \in \hat{X}$ , we have $\varphi(x) = x$ . For any $t = (t_1, \dots, t_n) \in \R^n$ , if $x = (x_1, \dots, x_n) = \varphi(t)$ , we have $0 \le t_i - x_i \le \frac{A - C}{b_i}$ and $C \le \ell(t) - \sum_{i=1}^n t_i b_i \le A$ . In fact, $\sum_{i=1}^n (t_i - x_i) b_i \le A - C$ .

Proof.

For the first statement, it suffices to show $x \in B_{x,\ell(x)}$ . But note that if $x \not\in B_{x,\ell(x)}$ , we would have $\ell(x) > \deg x$ and hence $B_{x,\ell(x)} \subseteq B_x$ , a contradiction.

For the second statement, note that $\ell(t) = \deg (x_1, \dots, x_n) \le \sum_{i=1}^n x_i b_i + A$ . Moreover, $B_{t,\ell} \neq \emptyset$ for $\ell = \sum_{i=1}^n t_i b_i + C$ , whence we get $\ell(t) - \sum_{i=1}^n t_i b_i \ge \ell - \sum_{i=1}^n t_i b_i = C$ . This shows the inequality on $\ell(t)$ . Now clearly $x_i \le t_i$ , whence $0 \le t_i - x_i$ . Now $A + \sum_{i=1}^n x_i b_i \ge \deg (x_1, \dots, x_n) = \ell(t) \ge C + \sum_{i=1}^n t_i b_i$ , whence $\sum_{i=1}^n (t_i - x_i) b_i \le A - C$ . As $t_i - x_i \ge 0$ .

□

Using Minima of Lattices.

In this section, we describe how to obtain $\hat{X}$ and $\varphi$ from an $(n + 1)$ -dimensional lattice $\Gamma \subseteq \R^{n+1}$ . We require that for every $t = (t_1, \dots, t_{n+1}) \in \Gamma$ , we either have $t = 0$ for $t_i \neq 0$ for all $i$ . More precisely, consider the map $N : \R^{n+1} \to \R$ , $(x_1, \dots, x_{n+1}) \mapsto \prod_{i=1}^n x_i$ . We assume that there exists a constant $c > 0$ with $N(x) \ge c$ for all $x \in \Gamma \setminus \{ 0 \}$ .

In fact, one can replace $\Gamma$ by any discrete subset with some additional properties which give similar results as Minkowski’s Lattice Point Theorem.

Definition.

A minimum of $\Gamma$ is an element $\mu = (\mu_1, \dots, \mu_{n+1}) \in \Gamma \setminus \{ 0 \}$ such that for all $z = (z_1, \dots, z_{n+1}) \in \Gamma$ with $\abs{z_i} \le \abs{\mu_i}$ for all $i$ , we either have $z = 0$ or $\abs{z_i} = \abs{\mu_i}$ for all $i$ . Denote the set of all minima by $\min \Gamma$ .

First, we will show that such minima exist:

Lemma.

Let $t = (t_1, \dots, t_{n+1}) \in \Gamma \setminus \{ 0 \}$ . Then there exists a minimum $\mu = (\mu_1, \dots, \mu_{n+1})$ of $\Gamma$ with $\abs{\mu_i} \le \abs{t_i}$ for all $i$ .

Proof.

This follows from the fact that $\Gamma$ is discrete. For $s = (s_1, \dots, s_{n+1})$ , define $\displaystyle B_s := \{ (x_1, \dots, x_{n+1} \in \Gamma \setminus \{ 0 \} \mid \abs{x_i} \le \abs{s_i} \text{ for all } i \}.$ As $\Gamma$ is discrete, $B_s$ is always finite.

In particular, $B_t$ is finite. Assume that $t$ is not a minimum (in which case we could choose $\mu = t$ ). Then there exists some $s = (s_1, \dots, s_{n+1}) \in B_t$ with $\abs{s_i} < \abs{t_i}$ for some $i$ . In that case, $s \in B_s \subsetneqq B_t$ . Now either $s$ is a minimum, in which case we choose $\mu = s$ , or it is not. In that case, we can repeat the procedure with $B_s$ instead of $B_t$ . As the size of these sets decreases every step and the sets are finite but non-empty, we eventually must find some $s \in B_t$ which is a minimum.

□

Define $\sim$ on $\R^{n+1}$ by $\displaystyle (s_1, \dots, s_{n+1}) \sim (t_1, \dots, t_{n+1}) :\Longleftrightarrow \forall i : \abs{s_i} = \abs{t_i},$ and consider the map $\displaystyle \Phi : \Gamma \setminus \{ 0 \} \to \R^n, \quad (t_1, \dots, t_{n+1}) = (\log \abs{t_1}, \dots, \log \abs{t_n}).$ First, $\Phi(a) = \Phi(b)$ if, and only if, $a \sim b$ . Let $\displaystyle \hat{X} := \Phi(\min \Gamma) = \{ \Phi(\mu) \mid \mu \text{ minimum of } \Gamma \}.$

Lemma.

Let $t = (t_1, \dots, t_n) \in \R^n$ . Then, there exists some $\mu = (\mu_1, \dots, \mu_n) \in \hat{X}$ with $0 \le t_i - x_i$ and $\sum_{i=1}^n (t_i - x_i) \le \log \abs{\det \Gamma}$ . In particular, $t_i - x_i \le \log \abs{\det \Gamma}$ .

Here, $\det{\Gamma}$ is the determinant of the lattice $\Gamma$ , i.e. the volume of one fundamental parallelepiped of $\Gamma$ .

Proof.

For $\ell > 0$ , consider the set $\displaystyle B_\ell := \{ (x_1, \dots, x_{n+1}) \in \R^{n+1} \mid \abs{x_i} \le \exp(t_i), \; \abs{x_{n+1}} \le \ell \}.$ By Minkowski’s Lattice Point Theorem, we have $B_\ell \cap \Gamma \neq 0$ for $\displaystyle 2^n \prod_{i=1}^n \exp(t_i) \cdot 2 \ell = \mathrm{vol}(B_\ell) > 2^{n+1} \abs{\det \Gamma},$ i.e. $\displaystyle \ell > \abs{\det \Gamma} \exp\biggl( -\sum_{i=1}^n t_i \biggr).$ Since $B_\ell$ is closed and $\Gamma$ discrete, a limit argument shows that this also holds for $\ell = \abs{\det \Gamma} \exp\bigl( -\sum_{i=1}^n t_i \bigr)$ . By the previous lemma, there exists a minimum $s = (s_1, \dots, s_{n+1})$ of $\Gamma$ which lies in $B_\ell$ ; let $\mu := (\mu_1, \dots, \mu_n) := \Phi(s)$ . Now $\mu_i = \log \abs{s_i} \le \log \exp(t_i) = t_i$ for $1 \le i \le n$ as $s \in B_\ell$ , whence $0 \le t_i - \mu_i$ .

Now $N(s) \ge c$ , whence $\sum_{i=1}^n \mu_i \ge \log c - \log \abs{s_{n+1}}$ . Now $\abs{s_{n+1}} \le \ell$ , whence $-\log \abs{s_{n+1}} \ge -\log \ell \ge -\log \abs{\det \Gamma} + \sum_{i=1}^n t_i$ . Therefore, we get $\displaystyle \sum_{i=1}^n \mu_i \ge -\log \abs{\det \Gamma} + \sum_{i=1}^n t_i,$ i.e. $\sum_{i=1}^n (t_i - \mu_i) \le \log \abs{\det \Gamma}$ .

□

Define $\Lambda := \{ x \in \R^n \mid \forall \mu \in \hat{X} : x + \mu \in \hat{X} \}$ ; this is a discrete subgroup of $\R^n$ . We assume that $\Lambda$ is a lattice in $\R^n$ , i.e. contains a basis of $\R^n$ . We can define $X$ and $d : X \to \R^n/\Lambda$ such that $\hat{X} = \pi^{-1}(d(X))$ , if $\pi : \R^n \to \R^n/\Lambda$ , $t \mapsto t + \Lambda$ is the projection. To get an $n$ -dimensional infrastructure, we are left to define $\varphi$ .

For that, we proceed as in the proof of the second lemma in this section. For $t = (t_1, \dots, t_n) \in \R^n$ , consider $\displaystyle B_\ell := \biggl\{ \Psi(x) \;\biggm| \begin{matrix} x = (x_1, \dots, x_{n+1}) \in \min \Gamma, \\ \abs{x_i} \le \exp(t_i), \; \abs{x_{n+1}} \le \ell \end{matrix} \biggr\}.$ Let $\ell > 0$ be minimal with $B_\ell \neq \emptyset$ , and let $\varphi(t) := \max_{\le} B_\ell$ . Then $\varphi(t)$ satisfies the properties in the statement of the lemma, i.e. lies near to $t$ itself. Moreover, one quickly checks that $\varphi(t + \lambda) = \varphi(t) + \lambda$ for all $\lambda \in \Lambda$ .

Hence, we obtain an $n$ -dimensional infrastructure.

Tags: infrastructure, n-dimensional, reduction

This entry was posted on tuesday, july 21st, 2009 at 05:43 utc and is filed under Algebra, Number Theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.