## Siegel's Lemma w. r. t. Maximum Norm and Sum–Distinct Sets

### by Iskander ALIEV

School of Mathematics University of Edinburgh James Clerk Maxwell Building King's Buildings, Mayfield Road Edinburgh EH9 3JZ, UK I.Aliev@ed.ac.uk Tel.: +44 131 650 5056 Fax: +44 131 650 6553
Abstract. Let $||\cdot ||$  denote the maximum norm. We show that for any non–zero vector $\mathbf{a}\in {\mathbb{Z}}^{n}$  , $n\ge 5$  , there exist linearly independent vectors ${\mathbf{x}}_{1},\dots ,{\mathbf{x}}_{n-1}\in {\mathbb{Z}}^{n}$  such that ${\mathbf{x}}_{i}\mathbf{a}=0$  , $i=1,\dots ,n-1$  and $0<||{\mathbf{x}}_{1}||\cdots ||{\mathbf{x}}_{n-1}||<\frac{||\mathbf{a}||}{{\sigma }_{n}},{\sigma }_{n}=\frac{2}{\pi }{\int }_{0}^{\infty }{\left(\frac{sint}{t}\right)}^{n}dt.$  This result implies a new lower bound on the greatest element of a sum–distinct set of positive integers (Erdös–Moser problem). The main tool is the Busemann theorem from convex geometry.
Keywords: sections of the cube, sinc integrals, Busemann's theorem, intersection body, successive minima 2000 MS Classification: 11H06, 11P70

1 Introduction

Let $\mathbf{a}=\left({a}_{1},\dots ,{a}_{n}\right)$  , $n\ge 2$  be a non–zero integral vector. Consider the linear equation
 $\begin{array}{ccc}{a}_{1}{x}_{1}+\dots +{a}_{n}{x}_{n}=0.& & \end{array}$ (1)
The (one–dimensional) Siegel Lemma w. r. t. maximum norm $||\cdot ||$  asks for an optimal constant ${c}_{n}>0$  such that ( 1 ) has an integral solution $\mathbf{x}=\left({x}_{1},\dots ,{x}_{n}\right)$  with
 $\begin{array}{ccc}0<||\mathbf{x}|{|}^{n-1}\le {c}_{n}||\mathbf{a}||.& & \end{array}$ (2)
The known exact values of ${c}_{n}$  are ${c}_{2}=1$  , ${c}_{3}=4/3$  and ${c}_{4}=27/19$  (see [1, [13). For $n=3,4$  the equality in ( 2 ) is not attained. A. Schinzel [13has shown that
 $\begin{array}{ccc}{c}_{n}=sup\Delta \left({\mathcal{ℋ}}_{{\alpha }_{1},\dots ,{\alpha }_{n-2}}^{n}{\right)}^{-1}\ge 1,& & \end{array}$
where $\Delta \left(\cdot \right)$  denotes the critical determinant, ${\mathcal{ℋ}}_{{\alpha }_{1},\dots ,{\alpha }_{n-2}}^{n}$  is a generalized hexagon given by
 $\begin{array}{ccc}|{x}_{i}|\le 1,i=1,\dots ,n,|{\sum }_{i=1}^{n-2}{\alpha }_{i}{x}_{i}+{x}_{n-1}+{x}_{n}|\le 1& & \end{array}$
and ${\alpha }_{i}$  run through all rational numbers in the interval $\left(0,1\right]$  . The values of ${c}_{n}$  for $n\le 4$  indicate that, most likely, ${c}_{n}=\Delta \left({\mathcal{ℋ}}_{1,\dots ,1}^{n}{\right)}^{-1}$  . However, a proof of this conjecture does not seem within reach at present. The best known upper bound
 $\begin{array}{ccc}{c}_{n}\le \sqrt{n}& & \end{array}$ (3)
easily follows from Theorem 1 of [3.
In the present paper we estimate ${c}_{n}$  via values of the sinc integrals
 $\begin{array}{ccc}{\sigma }_{n}=\frac{2}{\pi }{\int }_{0}^{\infty }{\left(\frac{sint}{t}\right)}^{n}dt.& & \end{array}$
Theorem. For any non–zero vector $\mathbf{a}\in {\mathbb{Z}}^{n}$  , $n\ge 5$  , there exist linearly independent vectors ${\mathbf{x}}_{1},\dots ,{\mathbf{x}}_{n-1}\in {\mathbb{Z}}^{n}$  such that ${\mathbf{x}}_{i}\mathbf{a}=0$  , $i=1,\dots ,n-1$  and
 $\begin{array}{ccc}0<||{\mathbf{x}}_{1}||\cdots ||{\mathbf{x}}_{n-1}||<\frac{||\mathbf{a}||}{{\sigma }_{n}}.& & \end{array}$ (4)
This result immediately implies the bound ${c}_{n}\le {\sigma }_{n}^{-1}$  . Since
 $\begin{array}{ccc}{\sigma }_{n}^{-1}\sim \sqrt{\frac{\pi n}{6}},\text{as}n\to \infty & & \end{array}$ (5)
(see Section  2 ), the theorem asymptotically improves the estimate ( 3 ). It is also known (see e. g. [12) that
 $\begin{array}{ccc}{\sigma }_{n}=\frac{n}{{2}^{n-1}}{\sum }_{0\le r
The sequences of numerators and denominators of ${\sigma }_{n}/2$  can be found in [15.
As it was observed by A. Schinzel (personal communication), Siegel's Lemma w. r.
t. maximum norm can be applied to the following well known problem from additive number theory. A finite set $\left\{{a}_{1},\dots ,{a}_{n}\right\}$  of integers is called sum–distinct set if any two of its ${2}^{n}$  subsums differ by at least $1$  . We shall assume w. l. o. g. that $0<{a}_{1}<{a}_{2}<\dots <{a}_{n}$  . In 1955, P. Erdös and L. Moser ([7, Problem 6) asked for an estimate on the least possible ${a}_{n}$  of such a set. They proved that ${a}_{n}>max\left\{{n}^{-1}{2}^{n},\frac{1}{4}{n}^{-1/2}{2}^{n}\right\}$  and Erdös conjectured that ${a}_{n}>{C}_{0}{2}^{n}$  , ${C}_{0}>0$  . In 1986, N. D. Elkies [6showed that ${a}_{n}>{2}^{-n}\left(\genfrac{}{}{0}{}{2n}{n}\right)$  and this result is cited by Guy ([10, Problem C8) as the best known lower bound for large $n$  . Following [6, note that references [7, 10state the problem equivalently in terms of ,,inverse function”. They ask to maximize the size $m$  of a sum–distinct subset of $\left\{1,2,\dots ,x\right\}$  , given $x$  . Clearly, the bound ${a}_{n}>{C}_{1}{n}^{-s}{2}^{n}$  corresponds to
 $\begin{array}{ccc}m<{log}_{2}x+s{log}_{2}{log}_{2}x+{log}_{2}\frac{1}{{C}_{1}}-o\left(1\right).& & \end{array}$
Corollary 1. For any sum–distinct set $\left\{{a}_{1},\dots ,{a}_{n}\right\}$  with $0<{a}_{1}<\dots <{a}_{n}$  , the inequality
 $\begin{array}{ccc}{a}_{n}>{\sigma }_{n}{2}^{n-1}& & \end{array}$
holds.
Since
 $\begin{array}{ccc}{2}^{-n}\left(\genfrac{}{}{0}{}{2n}{n}\right)\sim \frac{{2}^{n}}{\sqrt{\pi n}}\text{and}{\sigma }_{n}{2}^{n-1}\sim \frac{{2}^{n}}{\sqrt{\frac{2\pi n}{3}}},\text{as}n\to \infty ,& & \end{array}$
Corollary  1 asymptotically improves the result of Elkies with factor $\sqrt{3/2}$  .

2 Sections of the cube and sinc integrals

Let $C=\left[-1,1{\right]}^{n}\subset {\mathbb{R}}^{n}$  and let $\mathbf{s}=\left({s}_{1},\dots ,{s}_{n}\right)\in {\mathbb{R}}^{n}$  be a unit vector. It is a well known fact (see e. g. [2) that
 $\begin{array}{ccc}{\text{vol}}_{n-1}\left({\mathbf{s}}^{\perp }\cap C\right)=\frac{{2}^{n}}{\pi }{{\int }_{0}^{\infty }}^{n}{\prod }_{i=1}\frac{sin{s}_{i}t}{{s}_{i}t}dt,& & \end{array}$ (6)
where ${\mathbf{s}}^{\perp }$  is the $\left(n-1\right)$  –dimensional subspace orthogonal to $\mathbf{s}$  . In particular, the volume of the section orthogonal to the vertex $\mathbf{v}=\left(1,\dots ,1\right)$  of $C$  is given by
 $\begin{array}{ccc}{\text{vol}}_{n-1}\left({\mathbf{v}}^{\perp }\cap C\right)=\frac{{2}^{n}}{\pi }{\int }_{0}^{\infty }{\left(\frac{sin\frac{t}{\sqrt{n}}}{\frac{t}{\sqrt{n}}}\right)}^{n}dt={2}^{n-1}\sqrt{n}{\sigma }_{n}.& & \end{array}$
Laplace and Pólya (see [11, [14and e. g. [5) both gave proofs that
 $\begin{array}{ccc}{lim}_{n\to \infty }\frac{{\text{vol}}_{n-1}\left({\mathbf{v}}^{\perp }\cap C\right)}{{2}^{n-1}}=\sqrt{\frac{6}{\pi }}.& & \end{array}$
Thus, ( 5 ) is justified.
Lemma 1. For $n\ge 2$
 $\begin{array}{ccc}0<{\sigma }_{n+1}<{\sigma }_{n}\le 1.& & \end{array}$
• Proof. This result is implicit in [4. Indeed, Theorem 1 (ii) of [4applied with ${a}_{0}={a}_{1}=\dots ={a}_{n}=1$  gives the inequalities  $\begin{array}{ccc}0<{\sigma }_{n+1}\le {\sigma }_{n}\le 1.& & \end{array}$
The strict inequality ${\sigma }_{n+1}<{\sigma }_{n}$  follows easily from the observation that in this case the inequality in equation (3) of [4is strict with ${a}_{n+1}={a}_{0}=y=1$  .

3 An application of the Busemann theorem

Let $|\cdot |$  denote the euclidean norm. Recall that we can associate with each star body $L$  the distance function ${f}_{L}\left(\mathbf{x}\right)=inf\left\{\lambda >0:\mathbf{x}\in \lambda L\right\}.$  The intersection body $IL$  of a star body $L\subset {\mathbb{R}}^{n}$  , $n\ge 2$  is defined as the o–symmetric star body whose distance function ${f}_{IL}$  is given by
 $\begin{array}{ccc}{f}_{IL}\left(\mathbf{x}\right)=\frac{|\mathbf{x}|}{{\text{vol}}_{n-1}\left({\mathbf{x}}^{\perp }\cap L\right)}.& & \end{array}$
The Busemann theorem (see e. g. [8, Chapter 8) states that if $L$  is o–symmetric and convex, then $IL$  is the convex set. Let $f={f}_{IC}$  denote the distance function of $IC$  .
Lemma 2. For any non–zero $\mathbf{x}\in {\mathbb{R}}^{n}$
 $\begin{array}{ccc}f\left(\frac{\mathbf{x}}{||\mathbf{x}||}\right)\le f\left(\mathbf{v}\right)=\frac{1}{{\sigma }_{n}{2}^{n-1}},& & \end{array}$ (7)
with equality only if $n=2$  or $\frac{\mathbf{x}}{||\mathbf{x}||}$  is a vertex of the cube $C$  .
• Proof. We proceed by induction on $n$  . When $n=2$  the result is obvious. Suppose now ( 7 ) is true for $n-1\ge 2$  . Since, if some ${x}_{i}=0$  , the problem reduced to that in ${\mathbb{R}}^{n-1}$  , we may assume inductively that ${x}_{i}>0$  for all $i$  . Clearly, we may also assume that $\mathbf{w}=\frac{\mathbf{x}}{||\mathbf{x}||}$  is not a vertex of $C$  , in particular, $\mathbf{w}\ne \mathbf{v}$  .
Let $Q=\left[0,1{\right]}^{n}\subset {\mathbb{R}}^{n}$  and let $L$  be the $2$  –dimensional subspace spanned by vectors $\mathbf{v}$  and $\mathbf{x}$  . Then $P=L\cap Q$  is a parallelogram on the plane $L$  . To see this, observe that the cube $Q$  is the intersection of two cones $\left\{\mathbf{y}\in {\mathbb{R}}^{n}:{y}_{i}\ge 0\right\}$  and $\left\{\mathbf{y}\in {\mathbb{R}}^{n}:{y}_{i}\le 1\right\}$  with apexes at the points $\mathbf{o}$  and v respectively.
Suppose that $P$  has vertices $\mathbf{o}$  , $\mathbf{u}$  , $\mathbf{v}$  , $\mathbf{v}-\mathbf{u}$  . Then the edges $\mathbf{o}\mathbf{u}$  , $\mathbf{o}\mathbf{v}-\mathbf{u}$  of $P$  belong to coordinate hyperplanes and the edges $\mathbf{u}\mathbf{v}$  , $\mathbf{v}\mathbf{v}-\mathbf{u}$  lie on the boundary of $C$  . W. l.
o. g., we may assume that the point $\mathbf{w}$  lies on the edge $\mathbf{u}\mathbf{v}$  . Let  $\begin{array}{ccc}{\mathbf{v}}^{\prime }={\sigma }_{n}\mathbf{v}=\frac{{\text{vol}}_{n-1}\left({\mathbf{v}}^{\perp }\cap C\right)}{{2}^{n-1}}\frac{\mathbf{v}}{|\mathbf{v}|}\in \frac{1}{{2}^{n-1}}IC,& & \end{array}$
 $\begin{array}{ccc}{\mathbf{u}}^{\prime }={\sigma }_{n-1}\mathbf{u}.& & \end{array}$
Since the point $\mathbf{u}$  lies in one of the coordinate hyperplanes, by the induction hypothesis  $\begin{array}{ccc}f\left({\mathbf{u}}^{\prime }\right)=f\left({\sigma }_{n-1}\mathbf{u}\right)\le \frac{1}{{2}^{n-1}}.& & \end{array}$
Thus, ${\mathbf{u}}^{\prime }\in \frac{1}{{2}^{n-1}}IC$  . Consider the triangle with vertices $\mathbf{o}$  , $\mathbf{u}$  , $\mathbf{v}$  . Let ${\mathbf{w}}^{\prime }$  be the point of intersection of segments $\mathbf{o}\mathbf{w}$  and ${\mathbf{u}}^{\prime }{\mathbf{v}}^{\prime }$  . Observing that by Lemma  1   $\begin{array}{ccc}|{\sigma }_{n}\mathbf{w}|<|{\mathbf{w}}^{\prime }|<|{\sigma }_{n-1}\mathbf{w}|,& & \end{array}$
we get  $\begin{array}{ccc}\frac{1}{{\sigma }_{n-1}}<\frac{|\mathbf{w}|}{|{\mathbf{w}}^{\prime }|}<\frac{1}{{\sigma }_{n}}.& & \end{array}$ (8)
By the Busemann theorem $IC$  is convex. Therefore ${\mathbf{w}}^{\prime }\in \frac{1}{{2}^{n-1}}IC$  and thus  $\begin{array}{ccc}|{\mathbf{w}}^{\prime }|\le \frac{{\text{vol}}_{n-1}\left({\mathbf{w}}^{\perp }\cap C\right)}{{2}^{n-1}}.& & \end{array}$
By ( 8 ) we obtain  $\begin{array}{ccc}f\left(\frac{\mathbf{x}}{||\mathbf{x}||}\right)=f\left(\mathbf{w}\right)=\frac{|\mathbf{w}|}{{\text{vol}}_{n-1}\left({\mathbf{w}}^{\perp }\cap C\right)}\le \frac{|\mathbf{w}|}{{2}^{n-1}|{\mathbf{w}}^{\prime }|}<\frac{1}{{\sigma }_{n}{2}^{n-1}}.& & \end{array}$
Applying Lemma  2 to a unit vector $\mathbf{s}$  and using ( 6 ) we get the following inequality for sinc integrals.
Corollary 2. For any unit vector $\mathbf{s}=\left({s}_{1},\dots ,{s}_{n}\right)\in {\mathbb{R}}^{n}$
 $\begin{array}{ccc}||\mathbf{s}||{{\int }_{0}^{\infty }}^{n}{\prod }_{i=1}\frac{sin{s}_{i}t}{{s}_{i}t}dt\ge {\int }_{0}^{\infty }{\left(\frac{sint}{t}\right)}^{n}dt,& & \end{array}$
with equality only if $n=2$  or $\frac{\mathbf{s}}{||\mathbf{s}||}$  is a vertex of the cube $C$  .
Remark. Note that $IC$  is symmetric w. r. t. any coordinate hyperplane. This observation and Busemann's theorem immediately imply ( 7 ) with non–strict inequality in all cases.

4 Proof of the theorem

Clearly, we may assume that $||\mathbf{a}||>1$  and, in particular, that the inequality in Lemma  2 is strict for $\mathbf{x}=\mathbf{a}$  . We shall also assume w. l. o. g. that $gcd\left({a}_{1},\dots ,{a}_{n}\right)=1$  .
Let $S={\mathbf{a}}^{\perp }\cap C$  and $\Lambda ={\mathbf{a}}^{\perp }\cap {\mathbb{Z}}^{n}$  . Then $S$  is a centrally symmetric convex set and $\Lambda$  is a $\left(n-1\right)$  –dimensional sublattice of ${\mathbb{Z}}^{n}$  with determinant $det\Lambda =|\mathbf{a}|$  . Let ${\lambda }_{i}={\lambda }_{i}\left(S,\Lambda \right)$  be the $i$  –th successive minimum of $S$  w. r. t. $\Lambda$  , that is
 $\begin{array}{ccc}{\lambda }_{i}=inf\left\{\lambda >0:dim\left(\lambda S\cap \Lambda \right)\ge i\right\}.& & \end{array}$
We have to show that
 $\begin{array}{ccc}{\lambda }_{1}\cdots {\lambda }_{n-1}<\frac{||\mathbf{a}||}{{\sigma }_{n}}.& & \end{array}$
The $\left(n-1\right)$  –dimensional subspace ${\mathbf{a}}^{\perp }\subset {\mathbb{R}}^{n}$  can be considered as a usual $\left(n-1\right)$  –dimensional euclidean space. The Minkowski Theorem on Successive Minima (see e. g. [9, Chapter 2), applied to the $\mathbf{o}$  –symmetric convex set $S\subset {\mathbf{a}}^{\perp }$  and the lattice $\Lambda \subset {\mathbf{a}}^{\perp }$  , implies that
 $\begin{array}{ccc}{\lambda }_{1}\cdots {\lambda }_{n-1}\le \frac{{2}^{n-1}det\Lambda }{{\text{vol}}_{n-1}\left(S\right)}=\frac{{2}^{n-1}|\mathbf{a}|}{{\text{vol}}_{n-1}\left({\mathbf{a}}^{\perp }\cap C\right)}={2}^{n-1}f\left(\mathbf{a}\right),& & \end{array}$
and by Lemma  2 we get
 $\begin{array}{ccc}{\lambda }_{1}\cdots {\lambda }_{n-1}\le {2}^{n-1}f\left(\mathbf{a}\right)={2}^{n-1}f\left(\frac{\mathbf{a}}{||\mathbf{a}||}\right)||\mathbf{a}||& & \end{array}$
 $\begin{array}{ccc}<{2}^{n-1}f\left(\mathbf{v}\right)||\mathbf{a}||=\frac{||\mathbf{a}||}{{\sigma }_{n}}.& & \end{array}$
This proves the theorem.

5 Proof of Corollary  1

For a sum–distinct set $\left\{{a}_{1},\dots ,{a}_{n}\right\}$  consider the vector $\mathbf{a}=\left({a}_{1},\dots ,{a}_{n}\right)$  . Observe that any non–zero integral vector orthogonal to $\mathbf{a}$  must have the maximum norm greater than 1. Therefore ( 4 ) implies the inequality
 $\begin{array}{ccc}{2}^{n-1}<\frac{||\mathbf{a}||}{{\sigma }_{n}}.& & \end{array}$

6 Acknowledgements

The author wishes to thank Professors D. Borwein and A. Schinzel for valuable comments and Professor P. Gruber for fruitful discussions and suggestions. The work was partially supported by FWF Austrian Science Fund, project M821–N12. References

1. I. Aliev, On a Decomposition of Integer Vectors, PhD Dissertation, Institute of Mathematics PAN, Warsaw 2001.
2. K. Ball, Cube Slicing in ${\mathbb{R}}^{n}$  , Proc. Amer. Math. Soc. 97 (1986) no. 3 465–472.
3. E. Bombieri, J. Vaaler, On Siegel's Lemma, Invent. Math. 73 (1983) 11–32, Addendum, ibid. 75 (1984) 377.
4. D. Borwein, J. Borwein, Some Remarkable Properties of Sinc and Related Integrals, Ramanujan J. 5 (2001) no. 1 73–89.
5. D. Chakerian, D. Logothetti, Cube Slices, Pictorial Triangles, and Probability, Math. Mag. 64 (1991) no. 4 219–241.
6. N. D. Elkies, An Improved Lower Bound on the Greatest Element of a Sum-Distinct Set of Fixed Order, J. Combin. Theory Ser. A 41 (1986) no. 1 89–94.
7. P. Erdös, Problems and Results in Additive Number Theory, in ,,Colloque sur la Théorie des Nombres, Bruxelles, 1955”, pp. 136–137 (with L. Moser).
8. R. J. Gardner, Geometric Tomography, Encyclopedia of Mathematics and its Applications, 58, Cambridge University Press, Cambridge, 1995.
9. P. M. Gruber, C. G. Lekkerkerker, Geometry of Numbers, North–Holland, Amsterdam, 1987.
10. R. K. Guy, Unsolved Problems in Number Theory, Second edition. Problem Books in Mathematics. Unsolved Problems in Intuitive Mathematics, I. Springer-Verlag, New York, 1994.
11. P. S. Laplace, Théorie Analytique des Probabilités, Paris, 1812.
12. R. G. Medhurst, J. H. Roberts, Evaluation of the Integral ${I}_{n}\left(b\right)=\frac{2}{\pi }{\int }_{0}^{\infty }{\left(\frac{sinx}{x}\right)}^{n}cos\left(bx\right)dx$  , Math. Comp. 19 (1965) 113–117.
13. A. Schinzel, A Property of Polynomials with an Application to Siegel's Lemma, Monatsh. Math. 137 (2002) 239–251.
14. G. Pólya, Berechnung eines Bestimmten Integrals, Math. Ann. 74 (1913) 204–212.
15. N. J. A. Sloane, Sequences A049330 and A049331 in The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/ njas/sequences/.