The Art Gallery Guardian

Small L_1 norm solution to a linear Diophantine equation


Let a=(a_1,\ldots,a_n) be n integers with \gcd(a_1,\ldots,a_n)=1. There exists a integral vector x=(x_1,\ldots,x_n), such that \sum_{i=1}^n x_ia_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,\ldots,a_n) be a vector of positive integers with at least 2 elements, it does not contain 1 and \gcd(a)=1. If g_k = \gcd(a_k,\ldots,a_n), then there exist a solution to \displaystyle \sum_{i=1}^n x_i a_i = 1 such that for all 1\leq i\leq n-1, \displaystyle |x_i|\leq \frac{g_{i+1}}{2g_i} and |x_n|\leq \frac{\max(a_1,\ldots,a_{n-1})}{2}.

Theorem2

Let a be a vector of positive integers such that \gcd(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,\ldots,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 = \gcd(a_i,\ldots,a_n). Hence g_n = \min(a). We consider a solution to \sum_{i=1}^n x_ia_i = 1 satisfies Lemma 1. Let I = \set{i | g_{i+1}\geq 2g_{i}, i\leq n-1} and j=\min(I). One can algebraically check that a/b\leq a-b holds if both a\geq 2b 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\setminus \set{j}. \displaystyle \sum_{i\in I} |x_i| \leq \frac{1}{2} \sum_{i\in I} \frac{g_{i+1}}{g_i} \leq \frac{g_{j+1}}{2} + \frac{1}{2} \sum_{i\in I, i\neq j} g_{i+1} - g_i \leq \frac{g_{j+1}}{2} + \frac{1}{2} \sum_{i=j+1}^{n-1} g_{i+1}-g_i = \frac{1}{2}g_n = \frac{\min(a)}{2}.

\displaystyle \|x\| = \sum_{i=1}^n |x_i| = |x_n| + \sum_{i\in I} |x_i| \leq \frac{\min(a)+\max(a)}{2}

Corollary3

Let a be a vector of integers such that \gcd(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.