Summe der Produkte mit begrenzten Koeffizienten

Das folgende Lemma ist nicht schwer zu beweisen.

Lemma : Sei $c_1 \neq c_2 \neq \dots \neq c_r \in [n]$ und . Wenn ganze Zahlen sind (einige von ihnen können negativ sein), so dass , dann ganze Zahlen befriedigend , so dass . Hier Mittel für einige positive Konstante . $k \in [n]$ $m_1, m_2, \dots, m_r$ $m_1c_1 + m_2c_2 + \dots + m_rc_r = k$ $\exists$ $m'_1, m'_2, \dots,m'_r$ $m'_1c_1 + m'_2c_2 + \dots + m'_rc_r = k$ $|m'_1|+|m'_2|+\dots+|m'_r| \leq poly(n)$ $poly(n)$ $n^c$ $c$

Ich vermute, dass das obige Lemma bekannt ist. Ich suche eine Referenz des obigen Lemmas und die bestmögliche Bindung für . $poly(n)$

reference-request nt.number-theory Shiva Kintali
quelle

Crosspost bei MathOverflow: mathoverflow.net/questions/58034/…

Hsien-Chih Chang 張顯之

Antworten:

Eine -Bindung kann durch Bézouts Lemma erhalten werden : $O(n^2 \log r)$

$0 < c_i \leq n$ $\gcd(c_1,\ldots,c_r) = \sum_i m_i c_i$ $m_i$ $|m_i| \leq n \log r$

Dieses Lemma wird erhalten, indem Bézouts Lemma rekursiv auf zwei Variablen wird und die Identität . $\gcd(x_1,x_2,x_3) = \gcd(\gcd(x_1,x_2),x_3)$

ohne Verlust der Allgemeinheit an, dass indem Sie auf beiden Seiten von . Nach Bézouts Lemma existieren ganze Zahlen mit so dass $\gcd(c_1,\ldots,c_r) = 1$ $\gcd(c_1,\ldots,c_r)$ $\sum_i m_i c_i = k$ $m_i$ $|m_i| \leq n \log r$

k \cdot \sum_{i} m_{i} c_{i} = \sum_{i} (k \cdot m_{i}) c_{i} = k \cdot 1,

$k \cdot \sum_i m_i c_i = \sum_i (k \cdot m_i) c_i = k \cdot 1 \text,$

durch Beobachtung von wir das gewünschte mit . $k = O(n)$ $m'_i = k \cdot m_i$ $|m'_i| = O(n^2 \log r)$

Wenn Sie nach Literatur suchen, ist das Schlüsselwort inhomogene lineare diophantinische Gleichungen , die Gleichung wenn . Für die homogene kann man eine lineare Grenze für, siehe zB dieses oder dieses Papier . Was das inhomogene betrifft, so habe ich ein solches Ergebnis noch nicht gefunden; aber dieses Papier scheint relevant. $\sum_i m_i c_i = k$ $k = 0$ $|m_i'|$

Hsien-Chih Chang 張顯之
quelle

Ja. Ich habe

. Ich frage mich, ob bekannt ist, dass es

p o l y (n) = O (n^{3})

$poly(n) = O(n^3)$

O (n^{2})

$O(n^2)$

Shiva Kintali