5
$\begingroup$

This Wikipedia page currently quotes Bombieri and Vaaler's result on Siegel's lemma:

Suppose we are given a system of $m$ linear equations in $n$ unknowns such that $n>m$, say

$a_{11}x_1+\dots+a_{1n}x_n=0$

$\dots$

$a_{m1}x_1+\dots+a_{mn}x_n=0$

where the coefficients are rational integers, not all $0$, and bounded by $B$. The system then has a solution

$(x_1,x_2,\dots,x_n)$

with the $x$s all rational integers, not all $0$, and bounded by

$(nB)^{m/(n-m)}.$

Bombieri and Vaaler ($1983$) gave the following sharper bound for the $x$'s:

$\max|x_j|\leq\Big(D^{-1}\sqrt{\mathsf{det}(AA^T)}\Big)^{1/(n-m)}$

where $D$ is the greatest common divisor of the $m$ by $m$ minors of the matrix $A$, and $A^T$ is its transpose.

I want to know under what conditions on $A$ we can guarantee an '$\alpha$ - factor gap'. Denote $\Lambda$ to be set of solution vectors $(x_1,\dots,x_n)\in\Bbb Z^n$ for the system ($\Lambda$ is the kernel lattice).

Given $\alpha\in(0,1)$, '$\alpha$ - factor gap' guarantee basically means the inequality $$\alpha\Big(D^{-1}\sqrt{\mathsf{det}(AA^T)}\Big)^{1/(n-m)}\leq\min_{(x_1,\dots,x_n)\in\Lambda}\max|x_j|\leq\Big(D^{-1}\sqrt{\mathsf{det}(AA^T)}\Big)^{1/(n-m)}$$ is satisfied.

Let $\bf{x}_1,\bf{x}_2,\dots,\bf{x}_{n-m}\in\Bbb Z^n$ be full basis (each $\bf{x}_i\in\Bbb Z^n$) for solutions to the system (which is $\Lambda$). That is for every $(x_1,\dots,x_n)\in\Lambda$ there exists $r_1,\dots,r_{n-m}\in\Bbb Z$ such that $$(x_1,\dots,x_n)=r_1\bf{x}_1+\dots+r_{n-m}\bf{x}_{n-m}$$ holds.

At every $i\in\{1,\dots,n-m\}$ let $\lambda_{i,\infty}(\Lambda)$ be the $i$th successive minimum of kernel lattice in the $L^\infty$ norm.

  1. To guarantee an '$\alpha$ - factor gap's is it sufficient to show there is a $T\in\Bbb N$ such that $$\alpha^{n-m}T\leq \prod_{i=1}^{n-m}\lambda_{i,\infty}(\Lambda)\leq T$$ holds where $T$ is some suitable integer in $[0,(n-m)^{\frac{n-m}2}\mathsf{det}(\Lambda)]$?

  2. What is a sufficient condition if 1. does not work out?

Please also refer Bounded version of linear and quadratic Hasse--Minkowski theorem‌​and-quadratic-hasse-‌​minkowski-theorem.

Improve this question
$\endgroup$
16
  • $\begingroup$ why negvote???? $\endgroup$
    – Turbo
    Commented Sep 1, 2017 at 1:02
  • 1
    $\begingroup$ Bombieri and Vaaler prove a more precise result giving a full basis $\mathbf{x}_1, \ldots, \mathbf{x}_{N-M}$ of solutions such that the geometric mean $(\prod_{i=1}^{N-M} \max_j{|x_{ij}|})^{1/(N-M)}$ fulfills the same upper bound. For a fixed $\alpha \in (0,1)$, this implies in your question that your desired lower bound may not hold unless the discrete abelian group of integer solutions of $A.\mathbf{x} = 0$ has a basis of elements of nearly constant $L^{\infty}$-norm. This is an extremely stringent condition that 'holds with probability $0$' in any reasonable probabilistic sense. $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 2, 2017 at 19:53
  • 1
    $\begingroup$ You may also be interested in Vaaler's paper The best constant in Siegel's lemma (Monats. Math., 2003), which determines the sharpest possible form of the $L^2$ variant of Siegel's lemma, where your $\max(|X_j|)$ is replaced by the $L^2$-norm $\sqrt{\sum_{j=1}^N |X_j|^2 }$. $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 2, 2017 at 20:06
  • 1
    $\begingroup$ [My first comment above should read "$\ldots$ unless [it] has nearly equal successive minima for the $L^{\infty}$ norm." Not that it merely has a basis of about the same norm - sorry about this. If you now think of $A$ by duality as the $\mathbb{Z}$-module of integer solutions of $A.\mathbf{x} = 0$, and think of this as a random submodule of $\mathbb{Z}^N$ of rank $N-M$, you see how exceedingly rare is you requirement of a commensurable lower bound on the size of a non-zero solution. ] $\endgroup$
    – Vesselin Dimitrov
    Commented Sep 2, 2017 at 22:11
  • 1
    $\begingroup$ @VesselinDimitrov Why should the successive min criteria even be necessary? BV only prove basis where upper bound and geometric mean of quantity you quote agree. That does not preclude much shorter integer vectors in the subspace. On other hand there may be constructions where lower bound and upper bound agree. $\endgroup$
    – Turbo
    Commented Mar 4, 2018 at 9:15

0

Reset to default

You must log in to answer this question.