Return to Question

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Siegel's Lemma), it was stated that "Siegel's lemma is a corollary of the 'pigeonhole principle'". In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?

Here is Siegel's lemma:

Let $A$ be an $M$ $\times$ $N$ matrix with $M$ $\lt$ $N$ and having entries in $\bf Z$ of absolute value at most $Q$, where $\bf Z$ is the set of integers. Then there exists a nonzero vector $\bf x$ = ($x_{1}$, ..., $x_{n}$) $\in$ $\bf Z^{N}$ with $A$$\bf x$ = 0, such that

|$x_{i}$| $\leq$ [($N$$Q)^\frac {M} {(N - M)}$] =: $Z$, $i$ =1,...,$N$

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Siegel's Lemma), it was stated that "Siegel's lemma is a corollary of the 'pigeonhole principle'". In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?

Here is Siegel's lemma:

Let $A$ be an $M$ $\times$ $N$ matrix with $M$ $\lt$ $N$ and having entries in $\bf Z$ of absolute value at most $Q$, where $\bf Z$ is the set of integers. Then there exists a nonzero vector $\bf x$ = ($x_{1}$, ..., $x_{n}$) $\in$ $\bf Z^{N}$ with $A$$\bf x$ = 0, such that

|$x_{i}$| $\leq$ [($N$$Q)^\frac {M} {(N - M)}$] =: $Z$, $i$ =1,...,$N$

It should be noted that a weak form of $\Delta_{0}$$PHP$ [pigeonhole principle] is provable in $EFA$ as shown in Berarducci's and Intrigila's paper, "Combinatorial principles in elementary number theory", Annals of Pure and Applied Logic 55 (1991) 35-50, on pg. 36.

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Siegel's Lemma), it was stated that "Siegel's lemma is a corollary of the 'pigeonhole principle'". In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Siegel's Lemma), it was stated that "Siegel's lemma is a corollary of the 'pigeonhole principle'". In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?

Here is Siegel's lemma:

Let $A$ be an $M$ $\times$ $N$ matrix with $M$ $\lt$ $N$ and having entries in $\bf Z$ of absolute value at most $Q$, where $\bf Z$ is the set of integers. Then there exists a nonzero vector $\bf x$ = ($x_{1}$, ..., $x_{n}$) $\in$ $\bf Z^{N}$ with $A$$\bf x$ = 0, such that

|$x_{i}$| $\leq$ [($N$$Q)^\frac {M} {(N - M)}$] =: $Z$, $i$ =1,...,$N$

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Siegel's Lemma), it was stated that "Siegel's lemma is a corollary of the 'pigeonhole principle'" In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Siegel's Lemma), it was stated that "Siegel's lemma is a corollary of the 'pigeonhole principle'". In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?