5
$\begingroup$

Is there a kind of Siegel's Lemma saying that if $M$ is a ``small-height'' integer matrix, then there is a "small-height" vector $x$ with $\|Mx\|=\|M\|\|x\|$? (Here $\|Mx\|$ and $\|x\|$ denote the Euclidean norms, and $\|M\|$ is the operator norm, induced by the Euclidean norm.)

I am particularly interested in the case where the elements of $M$ are restricted to the values $0$ and $1$; what can be said in this situation about the vectors $x$ with $\|Mx\|=\|M\|\|x\|$ (or with the weaker property that, say, $\|Mx\|\ge 0.1\|M\|\|x\|$)? Can one guarantee that some of these vectors have, in some reasonable sense, a low height?

Improve this question
$\endgroup$
4
  • $\begingroup$ For beotians, could you give a formulation of Siegel's Lemma ? Thanks. $\endgroup$
    – Denis Serre
    Commented Dec 6, 2010 at 6:50
  • $\begingroup$ @Denis: Wikipedia has a brief and to-the-point article on Siegel's Lemma. (For some technical reason, I have troubles inserting the link.) $\endgroup$
    – Seva
    Commented Dec 6, 2010 at 9:38
  • $\begingroup$ Seva, without refereeing to your wanted case, I would suggest you looking at: Iskander Aliev, Siegel's lemma and sum-distinct sets. Discrete Comput. Geom. 39 (2008), no. 1-3, 59–66 (dx.doi.org/10.1007/s00454-008-9059-9), and Lenny Fukshansky, Siegel's lemma with additional conditions. J. Number Theory 120 (2006), no. 1, 13–25 (dx.doi.org/10.1016/j.jnt.2005.11.009). Iskander is an expert in all possible versions of Siegel's lemma... $\endgroup$
    – Wadim Zudilin
    Commented Dec 6, 2010 at 11:45
  • $\begingroup$ @Wadim: thanks for the references. I will check them but, honestly, I think the similarity between my question and Siegel's Lemma is merely conceptual. $\endgroup$
    – Seva
    Commented Dec 7, 2010 at 6:36

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .