Return to Question

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. Is it sufficient to show there is an $T\in\Bbb N$ such that $$\alpha^{n-m}T\leq \prod_{i=1}^{n-m}\lambda_{i,\infty}(\Lambda)\leq T$$ holds to guarantee we have an '$\alpha$ - factor gap' in $\min_{(x_1,\dots,x_n)\in\Lambda}\max|x_j|$ 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 https://mathoverflow.net/questions/280031/bounded-version-of-linear-‌​and-quadratic-hasse-‌​minkowski-theorem.

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 https://mathoverflow.net/questions/280031/bounded-version-of-linear-‌​and-quadratic-hasse-‌​minkowski-theorem.

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).

1. Given $\alpha\in(0,1)$, is there a condition on $A$ that guarantees $$\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)}?$$

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.

2. Is it sufficient to show there is an $T\in\Bbb N$ such that $$\alpha^{n-m}T\leq \prod_{i=1}^{n-m}\lambda_{i,\infty}(\Lambda)\leq T$$ holds to guarantee we have an '$\alpha$ - factor gap' in $\min_{(x_1,\dots,x_n)\in\Lambda}\max|x_j|$ where $m$ is some suitable integer in $[0,(n-m)^{\frac{n-m}2}\mathsf{det}(\Lambda)]$?

Please also refer https://mathoverflow.net/questions/280031/bounded-version-of-linear-‌​and-quadratic-hasse-‌​minkowski-theorem.

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. Is it sufficient to show there is an $T\in\Bbb N$ such that $$\alpha^{n-m}T\leq \prod_{i=1}^{n-m}\lambda_{i,\infty}(\Lambda)\leq T$$ holds to guarantee we have an '$\alpha$ - factor gap' in $\min_{(x_1,\dots,x_n)\in\Lambda}\max|x_j|$ 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 https://mathoverflow.net/questions/280031/bounded-version-of-linear-‌​and-quadratic-hasse-‌​minkowski-theorem.

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).

1. Given $\alpha\in(0,1)$, is there a condition on $A$ that guarantees $$\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)}?$$

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.

2. Is it sufficient to show there is an $T\in\Bbb N$ such that $$\alpha^{n-m}T\leq \prod_{i=1}^{n-m}\lambda_{i,\infty}(\Lambda)\leq T$$ holds to guarantee we have an '$\alpha$ - factor gap' in $\min_{(x_1,\dots,x_n)\in\Lambda}\max|x_j|$ where $m$ is some suitable integer in $[0,(n-m)^{\frac{n-m}2}\mathsf{det}(\Lambda)]$?

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).

1. Given $\alpha\in(0,1)$, is there a condition on $A$ that guarantees $$\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)}?$$

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.

2. Is it sufficient to show there is an $T\in\Bbb N$ such that $$\alpha^{n-m}T\leq \prod_{i=1}^{n-m}\lambda_{i,\infty}(\Lambda)\leq T$$ holds to guarantee we have an '$\alpha$ - factor gap' in $\min_{(x_1,\dots,x_n)\in\Lambda}\max|x_j|$ where $m$ is some suitable integer in $[0,(n-m)^{\frac{n-m}2}\mathsf{det}(\Lambda)]$?

Please also refer https://mathoverflow.net/questions/280031/bounded-version-of-linear-‌​and-quadratic-hasse-‌​minkowski-theorem.