How to Obtain Reduction Maps for n-dimensional Infrastructures.

So far, we have seen how -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 -dimensional case. We next want to motivate how a reduction map can be defined given and , 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

$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 : 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.

$\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 will consist of a finite set of ideals with bounded norms. The degree map will be the logarithm of the norm, and the '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

$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

$\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

$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

$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

$\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

$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

$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 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 -dimensional lattice $\Gamma \subseteq \R^{n+1}$ . We require that for every $t = (t_1, \dots, t_{n+1}) \in \Gamma$ , we either have for $t_i \neq 0$ for all . 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 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 , we either have or $\abs{z_i} = \abs{\mu_i}$ for all . 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 .

Proof.

This follows from the fact that $\Gamma$ is discrete. For $s = (s_1, \dots, s_{n+1})$ , define

$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, is always finite.

In particular, is finite. Assume that 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 . In that case, $s \in B_s \subsetneqq B_t$ . Now either is a minimum, in which case we choose $\mu = s$ , or it is not. In that case, we can repeat the procedure with instead of . 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

$(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

$\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

$\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

$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

$2^n \prod_{i=1}^n \exp(t_i) \cdot 2 \ell = \mathrm{vol}(B_\ell) > 2^{n+1} \abs{\det \Gamma},$

i.e.

$\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

$\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 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 -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

$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 itself. Moreover, one quickly checks that $\varphi(t + \lambda) = \varphi(t) + \lambda$ for all $\lambda \in \Lambda$ .

Hence, we obtain an -dimensional infrastructure.

Felix' Math Place

Focussed on, but not limited to Computational Number Theory

How to Obtain Reduction Maps for n-dimensional Infrastructures.

Constructing a Reduction Map.

Using Minima of Lattices.

Comments.

About Me.

About This Blog.

Overview Pages.

Recent Posts.

Archives.

Impressum.

Data Protection.

Felix' Math Place

Focussed on, but not limited to Computational Number Theory

How to Obtain Reduction Maps for n-dimensional Infrastructures.

Constructing a Reduction Map.

Using Minima of Lattices.

Comments.

About Me.

About This Blog.

Overview Pages.

Categories.

Recent Posts.

Archives.

Tags.

Impressum.

Data Protection.