The Art Gallery Guardian

Small L1L_1 norm solution to a linear Diophantine equation


Let a=(a1,,an)a=(a_1,\ldots,a_n) be nn integers with gcd(a1,,an)=1\gcd(a_1,\ldots,a_n)=1. There exists a integral vector x=(x1,,xn)x=(x_1,\ldots,x_n), such that i=1nxiai=1\sum_{i=1}^n x_ia_i = 1. How large is the solution xx? By Bézout's lemma, when n=2n=2, we can obtain that xa\|x\|\leq \|a\|. Here \|\cdot \| is the L1L_1 norm.

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

Lemma1

Let a=(a1,,an)a=(a_1,\ldots,a_n) be a vector of positive integers with at least 22 elements, it does not contain 11 and gcd(a)=1\gcd(a)=1. If gk=gcd(ak,,an)g_k = \gcd(a_k,\ldots,a_n), then there exist a solution to i=1nxiai=1\displaystyle \sum_{i=1}^n x_i a_i = 1 such that for all 1in11\leq i\leq n-1, xigi+12gi\displaystyle |x_i|\leq \frac{g_{i+1}}{2g_i} and xnmax(a1,,an1)2|x_n|\leq \frac{\max(a_1,\ldots,a_{n-1})}{2}.

Theorem2

Let aa be a vector of positive integers such that gcd(a)=1\gcd(a)=1, then there exists a integral solution to xa=1x \cdot a=1 such that x12(min(a)+max(a))\|x\|\leq \frac{1}{2}(\min(a)+\max(a)).

Proof

Let a=(a1,,an)a=(a_1,\ldots,a_n). Let an=min(a)a_n=\min(a). We can assume 11 is not in aa, otherwise we can find xx such that x=1\|x\|=1. Let gi=gcd(ai,,an)g_i = \gcd(a_i,\ldots,a_n). Hence gn=min(a)g_n = \min(a). We consider a solution to i=1nxiai=1\sum_{i=1}^n x_ia_i = 1 satisfies Lemma 1. Let I={igi+12gi,in1}I = \set{i | g_{i+1}\geq 2g_{i}, i\leq n-1} and j=min(I)j=\min(I). One can algebraically check that a/baba/b\leq a-b holds if both a2ba\geq 2b and b2b\geq 2. In particular, we have gi+1gigi+1gi\frac{g_{i+1}}{g_i} \leq g_{i+1}-g_i for all iI{j}i\in I\setminus \set{j}. iIxi12iIgi+1gigj+12+12iI,ijgi+1gigj+12+12i=j+1n1gi+1gi=12gn=min(a)2.\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}.

x=i=1nxi=xn+iIximin(a)+max(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 aa be a vector of integers such that gcd(a)=1\gcd(a)=1, then there exists a integral solution to xa=1x \cdot a=1 such that xa\|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 .
Tags: number theory.