Small $L_{1}$ norm solution to a linear Diophantine equation

Let $a = (a_{1}, \dots, a_{n})$ be $n$ integers with $g cd (a_{1}, \dots, a_{n}) = 1$ . There exists a integral vector $x = (x_{1}, \dots, x_{n})$ , such that $\sum_{i = 1}^{n} x_{i} a_{i} = 1$ . How large is the solution $x$ ? By Bézout’s lemma, when $n = 2$ , we can obtain that $∥ x ∥ \leq ∥ a ∥$ . Here $∥ \cdot ∥$ is the $L_{1}$ norm.

However, I could not find a general bound of $∥ x ∥$ anywhere. Here we prove that the bound on $∥ x ∥$ is true in general. Before that, we first introduce a lemma from [1].

Lemma1

Let $a = (a_{1}, \dots, a_{n})$ be a vector of positive integers with at least $2$ elements, it does not contain $1$ and $g cd (a) = 1$ . If $g_{k} = g cd (a_{k}, \dots, a_{n})$ , then there exist a solution to $i = 1 \sum n x_{i} a_{i} = 1$ such that for all $1 \leq i \leq n - 1$ , $∣ x_{i} ∣ \leq \frac{g _{i + 1}}{2 g _{i}}$ and $∣ x_{n} ∣ \leq \frac{m a x ( a _{1} , \dots , a _{n - 1} )}{2}$ .

Theorem2

Let $a$ be a vector of positive integers such that $g cd (a) = 1$ , then there exists a integral solution to $x \cdot a = 1$ such that $∥ x ∥ \leq \frac{1}{2} (min (a) + max (a))$ .

Proof

Let $a = (a_{1}, \dots, a_{n})$ . Let $a_{n} = min (a)$ . We can assume $1$ is not in $a$ , otherwise we can find $x$ such that $∥ x ∥ = 1$ . Let $g_{i} = g cd (a_{i}, \dots, a_{n})$ . Hence $g_{n} = min (a)$ . We consider a solution to $\sum_{i = 1}^{n} x_{i} a_{i} = 1$ satisfies Lemma 1. Let $I = {i ∣ g_{i + 1} \geq 2 g_{i}, i \leq n - 1}$ and $j = min (I)$ . One can algebraically check that $a / b \leq a - b$ holds if both $a \geq 2 b$ and $b \geq 2$ . In particular, we have $\frac{g _{i + 1}}{g _{i}} \leq g_{i + 1} - g_{i}$ for all $i \in I ∖ {j}$ . $i \in I \sum ∣ x_{i} ∣ \leq \frac{1}{2} i \in I \sum \frac{g _{i + 1}}{g _{i}} \leq \frac{g _{j + 1}}{2} + \frac{1}{2} i \in I, i \neq = j \sum g_{i + 1} - g_{i} \leq \frac{g _{j + 1}}{2} + \frac{1}{2} i = j + 1 \sum n - 1 g_{i + 1} - g_{i} = \frac{1}{2} g_{n} = \frac{min ( a )}{2} .$

$∥ x ∥ = i = 1 \sum n ∣ x_{i} ∣ = ∣ x_{n} ∣ + i \in I \sum ∣ x_{i} ∣ \leq \frac{min ( a ) + max ( a )}{2}$

Corollary3

Let $a$ be a vector of integers such that $g cd (a) = 1$ , then there exists a integral solution to $x \cdot a = 1$ such that $∥ x ∥ \leq ∥ a ∥$ .

References

[1]

D. Ford, G. Havas, A new algorithm and refined bounds for extended gcd computation, in: H. Cohen (Ed.), Algorithmic Number Theory: Second International Symposium, ANTS-II Talence, France, May 18–23, 1996 Proceedings, Springer Berlin Heidelberg, Berlin, Heidelberg, 1996: pp. 145–150 10.1007/3-540-61581-4_50.

Posted by Chao Xu on 2017-08-26.

Tags: number theory.

Small L1​ norm solution to a linear Diophantine equation

References

Small $L_{1}$ norm solution to a linear Diophantine equation