Suma de productos con coeficientes acotados

8

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 enterosc1c2cr[n]k[n]m1,m2,,mrm1c1+m2c2++mrcr=k satisfactorio m 1 c 1 + m 2 c 2 + + m r c r = k tal que | m 1 | + | m 2 | + + | m r | p o lm1,m2,,mrm1c1+m2c2++mrcr=k . Aquí p o l y ( n ) significa n c para alguna constante positiva c .|m1|+|m2|++|mr|poly(n)poly(n)ncc

Supongo que el lema anterior es bien conocido. Estoy buscando una referencia del lema anterior y el mejor límite posible para .poly(n)

Shiva Kintali
fuente
1
Crosspost en MathOverflow: mathoverflow.net/questions/58034/…
Hsien-Chih Chang 張顯 之

Respuestas:

5

Se puede obtener un límite mediante el lema de Bézout :O(n2logr)

0<cingcd(c1,,cr)=imicimi|mi|nlogr

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)=1gcd(c1,,cr)imici=kmi|mi|nlogr

kimici=i(kmi)ci=k1,

observando tenemos el con .k=O(n)mi=kmi|mi|=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=kk=0|mi|

Hsien-Chih Chang 張顯 之
fuente
Si. Tengo . Me pregunto si se sabe que es . poly(n)=O(n3)O(n2)
Shiva Kintali