Two questions regarding the reverse mathematics of Siegel's lemma 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:

*

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


*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.
 A: I believe I have found a partial answer to my question.  Consider the following:  If the first-order part of $RCA^{*}_0$ is $I$$\Delta_{0}$ + $Exp$ + $B$$\Sigma_{1}$, where $B$$\Sigma_{1}$ is the Boundedness principle for $\Sigma_{1}$ formulas (as Prof. Enayat suggests in his comment to his answer to the mathoverflow question question, "van der Waerden's theorem in Reverse Mathematics" (question 316480)), one can use the following theorem of Dimitracopoulos and Paris (mentioned in the paper "Where Pigeonhole Principles Meet Konig Lemmas")

Over $I$$\Delta_{0}$ + $Exp$,
$\forall$ $x$($\Sigma_{1}$:  $x$ +$1$ $\rightarrow$ $($ 2 $)^{1}_{x}$$)$ is equivalent to $B$$\Sigma_{1}$, where $\forall$$ $x$ $($\Sigma_{1}$:  $x$ + $1$ $\rightarrow$ $($ 2 $)^{1}_{x}$$)$ is the $\Sigma^{0}_{1}$ Pigeonhole Principle

to substitute the $\Sigma^{0}_{1}$ Pigeonhole Principle for $B$$\Sigma_{1}$ in the first-order part of $RCA^{*}_{0}$, giving the type of pigeonhole principle needed to prove Siegel's Lemma in $EFA$, if it in fact can be....
