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 \[ \sum_{i=1}^n x_i a_i = 1 \] such that for all \(1\leq i\leq n-1\), \[ |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}\). \[ \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}. \]

\[ \|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.