MathLabs

第5题

考虑关于 q=2pq=2p 个未知数 x1,…,xqx_1,\ldots,x_q 的 pp 个方程，其中每个系数 aija_{ij} 都属于 {−1,0,1}\{-1,0,1\}。证明该方程组存在一个解，使得：(a) 所有 xjx_j 都是整数；(b) 至少有一个 xj≠0x_j\ne0；(c) 对每个 jj 都有 ∣xj∣≤q|x_j|\le q。
第 2/5 步：限制一个线性形式
上一步下一步
通俗地说

无论系数如何排列，每一行只有 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 个整数值。