MathLabs

第5問

pp 本の方程式からなる、q=2pq=2p 個の未知数 x1,…,xqx_1,\ldots,x_q の連立方程式を考える。すべての係数 aija_{ij} は {−1,0,1}\{-1,0,1\} に属する。この系が (a) すべての xjx_j が整数、(b) 少なくとも1つの xj≠0x_j\ne0、(c) すべての jj で ∣xj∣≤q|x_j|\le q を満たす解を持つことを証明せよ。
ステップ 2/5: 1つの線形形式を評価する
ざっくり言うと

係数の並び方によらず、各行が取り得る出力は q2+1q^2+1 通りに限られる。

−q2≤∑i=1qajixi≤q2-q^2\le\sum_{i=1}^q a_{ji}x_i\le q^2
詳しい解説

固定した行 jj について、線形形式 Lj=∑i=1qajixiL_j=\sum_{i=1}^q a_{ji}x_i の最大値と最小値の差は高々 q⋅q=q2q\cdot q=q^2 である。これは係数が {−1,0,1}\{-1,0,1\} に属し、各 xix_i が [0,q][0,q] に属するためである。したがって、LjL_j が取り得る整数値は高々 q2+1q^2+1 個である。