El siguiente lema no es difícil de probar.
Lema : Sea y k ∈ [ n ] . Si m 1 , m 2 , ... , m r son enteros (algunos de ellos pueden ser negativos) de modo que m 1 c 1 + m 2 c 2 + ⋯ + m r c r = k , entonces ∃ enteros satisfactorio m ′ 1 c 1 + m ′ 2 c 2 + ⋯ + m ′ r c r = k tal que | m ′ 1 | + | m ′ 2 | + ⋯ + | m ′ r | ≤ p o l . Aquí p o l y ( n ) significa n c para alguna constante positiva c .
Supongo que el lema anterior es bien conocido. Estoy buscando una referencia del lema anterior y el mejor límite posible para .
reference-request
nt.number-theory
Shiva Kintali
fuente
fuente
Respuestas:
Se puede obtener un límite mediante el lema de Bézout :O(n2logr)
Este lema se obtiene aplicando recursivamente el lema de Bézout en dos variables y la identidad .gcd(x1,x2,x3)=gcd(gcd(x1,x2),x3)
Sin pérdida de generalidad, suponga que dividiendo en ambos lados de . Según el lema de Bézout, existen enteros con tal quegcd(c1,…,cr)=1 gcd(c1,…,cr) ∑imici=k mi |mi|≤nlogr
observando tenemos el con .k=O(n) m′i=k⋅mi |m′i|=O(n2logr)
Si está buscando literatura, la palabra clave es ecuaciones lineales de diofantina no homogéneas , es decir, la ecuación cuando . Para el homogéneo, se puede obtener un límite lineal en, ver por ejemplo este o este artículo . En cuanto al no homogéneo, todavía no he encontrado ese resultado; Sin embargo, este artículo parece relevante.∑imici=k k=0 |m′i|
fuente