Siegel's Lemma w. r. t. Maximum Norm and Sum

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

a \in Z^{n}

n \geq 5

, there exist linearly independent vectors

x_{1}, \dots, x_{n - 1} \in Z^{n}

such that

x_{i} a = 0

i = 1, \dots, n - 1

and

0 < | | x_{1} | | \dots | | x_{n - 1} | | < \frac{| | a | |}{σ_{n}}, σ_{n} = \frac{2}{π} \int_{0}^{\infty} {(\frac{sin t}{t})}^{n} d t .

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

a = (a_{1}, \dots, a_{n})

n \geq 2

be a non–zero integral vector. Consider the linear equation

\begin{matrix} a_{1} x_{1} + \dots + a_{n} x_{n} = 0 . \end{matrix}

(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

x = (x_{1}, \dots, x_{n})

with

\begin{matrix} 0 < | | x | |^{n - 1} \leq c_{n} | | a | | . \end{matrix}

(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 [13] has shown that

\begin{matrix} c_{n} = sup Δ (ℋ_{α_{1}, \dots, α_{n - 2}}^{n})^{- 1} \geq 1, \end{matrix}

where

Δ (\cdot)

denotes the critical determinant,

ℋ_{α_{1}, \dots, α_{n - 2}}^{n}

is a generalized hexagon given by

\begin{matrix} | x_{i} | \leq 1, i = 1, \dots, n, | \sum_{i = 1}^{n - 2} α_{i} x_{i} + x_{n - 1} + x_{n} | \leq 1 \end{matrix}

and

α_{i}

run through all rational numbers in the interval

(0, 1]

. The values of

c_{n}

for

n \leq 4

indicate that, most likely,

c_{n} = Δ (ℋ_{1, \dots, 1}^{n})^{- 1}

. However, a proof of this conjecture does not seem within reach at present. The best known upper bound

\begin{matrix} c_{n} \leq \sqrt{n} \end{matrix}

(3)

easily follows from Theorem 1 of [3] .

In the present paper we estimate

c_{n}

via values of the sinc integrals

\begin{matrix} σ_{n} = \frac{2}{π} \int_{0}^{\infty} {(\frac{sin t}{t})}^{n} d t . \end{matrix}

Theorem. For any non–zero vector

a \in Z^{n}

n \geq 5

, there exist linearly independent vectors

x_{1}, \dots, x_{n - 1} \in Z^{n}

such that

x_{i} a = 0

i = 1, \dots, n - 1

and

\begin{matrix} 0 < | | x_{1} | | \dots | | x_{n - 1} | | < \frac{| | a | |}{σ_{n}} . \end{matrix}

(4)

This result immediately implies the bound

c_{n} \leq σ_{n}^{- 1}

. Since

\begin{matrix} σ_{n}^{- 1} \sim \sqrt{\frac{π n}{6}}, as n \to \infty \end{matrix}

(5)

(see Section 2 ), the theorem asymptotically improves the estimate ( 3 ). It is also known (see e. g. [12] ) that

\begin{matrix} σ_{n} = \frac{n}{2^{n - 1}} \sum_{0 \leq r < n / 2, r \in Z} \frac{(- 1)^{r} (n - 2 r)^{n - 1}}{r! (n - r)!} . \end{matrix}

The sequences of numerators and denominators of

σ_{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

{a_{1}, \dots, a_{n}}

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 {n^{- 1} 2^{n}, \frac{1}{4} n^{- 1 / 2} 2^{n}}

and Erdös conjectured that

a_{n} > C_{0} 2^{n}

C_{0} > 0

. In 1986, N. D. Elkies [6] showed that

a_{n} > 2^{- n} (\binom{2 n}{n})

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, 10] state the problem equivalently in terms of ,,inverse function”. They ask to maximize the size

m

of a sum–distinct subset of

{1, 2, \dots, x}

, given

x

. Clearly, the bound

a_{n} > C_{1} n^{- s} 2^{n}

corresponds to

\begin{matrix} m < {log}_{2} x + s {log}_{2} {log}_{2} x + {log}_{2} \frac{1}{C_{1}} - o (1) . \end{matrix}

Corollary 1. For any sum–distinct set

{a_{1}, \dots, a_{n}}

with

0 < a_{1} < \dots < a_{n}

, the inequality

\begin{matrix} a_{n} > σ_{n} 2^{n - 1} \end{matrix}

holds.

Since

\begin{matrix} 2^{- n} (\binom{2 n}{n}) \sim \frac{2^{n}}{\sqrt{π n}} and σ_{n} 2^{n - 1} \sim \frac{2^{n}}{\sqrt{\frac{2 π n}{3}}}, as n \to \infty, \end{matrix}

Corollary 1 asymptotically improves the result of Elkies with factor

\sqrt{3 / 2}

2 Sections of the cube and sinc integrals

Let

C = [- 1, 1]^{n} \subset R^{n}

and let

s = (s_{1}, \dots, s_{n}) \in R^{n}

be a unit vector. It is a well known fact (see e. g. [2] ) that

\begin{matrix} {vol}_{n - 1} (s^{⊥} \cap C) = \frac{2^{n}}{π} {\int_{0}^{\infty}}^{n} \prod_{i = 1} \frac{sin s_{i} t}{s_{i} t} d t, \end{matrix}

(6)

where

s^{⊥}

is the

(n - 1)

–dimensional subspace orthogonal to

s

. In particular, the volume of the section orthogonal to the vertex

v = (1, \dots, 1)

C

is given by

\begin{matrix} {vol}_{n - 1} (v^{⊥} \cap C) = \frac{2^{n}}{π} \int_{0}^{\infty} {(\frac{sin \frac{t}{\sqrt{n}}}{\frac{t}{\sqrt{n}}})}^{n} d t = 2^{n - 1} \sqrt{n} σ_{n} . \end{matrix}

Laplace and Pólya (see [11] , [14] and e. g. [5] ) both gave proofs that

\begin{matrix} {lim}_{n \to \infty} \frac{{vol}_{n - 1} (v^{⊥} \cap C)}{2^{n - 1}} = \sqrt{\frac{6}{π}} . \end{matrix}

Thus, ( 5 ) is justified.

Lemma 1. For

n \geq 2

\begin{matrix} 0 < σ_{n + 1} < σ_{n} \leq 1 . \end{matrix}

Proof. This result is implicit in [4] . Indeed, Theorem 1 (ii) of [4] applied with $a_{0} = a_{1} = \dots = a_{n} = 1$ gives the inequalities
$\begin{matrix} 0 < σ_{n + 1} \leq σ_{n} \leq 1 . \end{matrix}$
The strict inequality $σ_{n + 1} < σ_{n}$ follows easily from the observation that in this case the inequality in equation (3) of [4] is 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} (x) = inf {λ > 0 : x \in λ L} .

The intersection body

I L

of a star body

L \subset R^{n}

n \geq 2

is defined as the o–symmetric star body whose distance function

f_{I L}

is given by

\begin{matrix} f_{I L} (x) = \frac{| x |}{{vol}_{n - 1} (x^{⊥} \cap L)} . \end{matrix}

The Busemann theorem (see e. g. [8] , Chapter 8) states that if

L

is o–symmetric and convex, then

I L

is the convex set. Let

f = f_{I C}

denote the distance function of

I C

Lemma 2. For any non–zero

x \in R^{n}

\begin{matrix} f (\frac{x}{| | x | |}) \leq f (v) = \frac{1}{σ_{n} 2^{n - 1}}, \end{matrix}

(7)

with equality only if

n = 2

\frac{x}{| | 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 \geq 2

. Since, if some

x_{i} = 0

, the problem reduced to that in

R^{n - 1}

, we may assume inductively that

x_{i} > 0

for all

i

. Clearly, we may also assume that

w = \frac{x}{| | x | |}

is not a vertex of

C

, in particular,

w \neq v

Let

Q = [0, 1]^{n} \subset R^{n}

and let

L

be the

2

–dimensional subspace spanned by vectors

v

and

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

{y \in R^{n} : y_{i} \geq 0}

and

{y \in R^{n} : y_{i} \leq 1}

with apexes at the points

o

and v respectively.

Suppose that

P

has vertices

o

u

v

v - u

. Then the edges

o u

o v - u

P

belong to coordinate hyperplanes and the edges

u v

v v - u

lie on the boundary of

C

. W. l.

o. g., we may assume that the point

w

lies on the edge

u v

. Let

\begin{matrix} v^{'} = σ_{n} v = \frac{{vol}_{n - 1} (v^{⊥} \cap C)}{2^{n - 1}} \frac{v}{| v |} \in \frac{1}{2^{n - 1}} I C, \end{matrix}

\begin{matrix} u^{'} = σ_{n - 1} u . \end{matrix}

Since the point

u

lies in one of the coordinate hyperplanes, by the induction hypothesis

\begin{matrix} f (u^{'}) = f (σ_{n - 1} u) \leq \frac{1}{2^{n - 1}} . \end{matrix}

Thus,

u^{'} \in \frac{1}{2^{n - 1}} I C

. Consider the triangle with vertices

o

u

v

. Let

w^{'}

be the point of intersection of segments

o w

and

u^{'} v^{'}

. Observing that by Lemma 1

\begin{matrix} | σ_{n} w | < | w^{'} | < | σ_{n - 1} w |, \end{matrix}

we get

\begin{matrix} \frac{1}{σ_{n - 1}} < \frac{| w |}{| w^{'} |} < \frac{1}{σ_{n}} . \end{matrix}

(8)

By the Busemann theorem

I C

is convex. Therefore

w^{'} \in \frac{1}{2^{n - 1}} I C

and thus

\begin{matrix} | w^{'} | \leq \frac{{vol}_{n - 1} (w^{⊥} \cap C)}{2^{n - 1}} . \end{matrix}

By ( 8 ) we obtain

\begin{matrix} f (\frac{x}{| | x | |}) = f (w) = \frac{| w |}{{vol}_{n - 1} (w^{⊥} \cap C)} \leq \frac{| w |}{2^{n - 1} | w^{'} |} < \frac{1}{σ_{n} 2^{n - 1}} . \end{matrix}

Applying Lemma 2 to a unit vector

s

and using ( 6 ) we get the following inequality for sinc integrals.

Corollary 2. For any unit vector

s = (s_{1}, \dots, s_{n}) \in R^{n}

\begin{matrix} | | s | | {\int_{0}^{\infty}}^{n} \prod_{i = 1} \frac{sin s_{i} t}{s_{i} t} d t \geq \int_{0}^{\infty} {(\frac{sin t}{t})}^{n} d t, \end{matrix}

with equality only if

n = 2

\frac{s}{| | s | |}

is a vertex of the cube

C

Remark. Note that

I C

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

| | a | | > 1

and, in particular, that the inequality in Lemma 2 is strict for

x = a

. We shall also assume w. l. o. g. that

gcd (a_{1}, \dots, a_{n}) = 1

Let

S = a^{⊥} \cap C

and

Λ = a^{⊥} \cap Z^{n}

. Then

S

is a centrally symmetric convex set and

Λ

is a

(n - 1)

–dimensional sublattice of

Z^{n}

with determinant

det Λ = | a |

. Let

λ_{i} = λ_{i} (S, Λ)

be the

i

–th successive minimum of

S

w. r. t.

Λ

, that is

\begin{matrix} λ_{i} = inf {λ > 0 : dim (λ S \cap Λ) \geq i} . \end{matrix}

We have to show that

\begin{matrix} λ_{1} \dots λ_{n - 1} < \frac{| | a | |}{σ_{n}} . \end{matrix}

The

(n - 1)

–dimensional subspace

a^{⊥} \subset R^{n}

can be considered as a usual

(n - 1)

–dimensional euclidean space. The Minkowski Theorem on Successive Minima (see e. g. [9] , Chapter 2), applied to the

o

–symmetric convex set

S \subset a^{⊥}

and the lattice

Λ \subset a^{⊥}

, implies that

\begin{matrix} λ_{1} \dots λ_{n - 1} \leq \frac{2^{n - 1} det Λ}{{vol}_{n - 1} (S)} = \frac{2^{n - 1} | a |}{{vol}_{n - 1} (a^{⊥} \cap C)} = 2^{n - 1} f (a), \end{matrix}

and by Lemma 2 we get

\begin{matrix} λ_{1} \dots λ_{n - 1} \leq 2^{n - 1} f (a) = 2^{n - 1} f (\frac{a}{| | a | |}) | | a | | \end{matrix}

\begin{matrix} < 2^{n - 1} f (v) | | a | | = \frac{| | a | |}{σ_{n}} . \end{matrix}

This proves the theorem.

5 Proof of Corollary 1

For a sum–distinct set

{a_{1}, \dots, a_{n}}

consider the vector

a = (a_{1}, \dots, a_{n})

. Observe that any non–zero integral vector orthogonal to

a

must have the maximum norm greater than 1. Therefore ( 4 ) implies the inequality

\begin{matrix} 2^{n - 1} < \frac{| | a | |}{σ_{n}} . \end{matrix}

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

I. Aliev, On a Decomposition of Integer Vectors, PhD Dissertation, Institute of Mathematics PAN, Warsaw 2001.
K. Ball, Cube Slicing in $R^{n}$ , Proc. Amer. Math. Soc. 97 (1986) no. 3 465–472.
E. Bombieri, J. Vaaler, On Siegel's Lemma, Invent. Math. 73 (1983) 11–32, Addendum, ibid. 75 (1984) 377.
D. Borwein, J. Borwein, Some Remarkable Properties of Sinc and Related Integrals, Ramanujan J. 5 (2001) no. 1 73–89.
D. Chakerian, D. Logothetti, Cube Slices, Pictorial Triangles, and Probability, Math. Mag. 64 (1991) no. 4 219–241.
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.
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).
R. J. Gardner, Geometric Tomography, Encyclopedia of Mathematics and its Applications, 58, Cambridge University Press, Cambridge, 1995.
P. M. Gruber, C. G. Lekkerkerker, Geometry of Numbers, North–Holland, Amsterdam, 1987.
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.
P. S. Laplace, Théorie Analytique des Probabilités, Paris, 1812.
R. G. Medhurst, J. H. Roberts, Evaluation of the Integral $I_{n} (b) = \frac{2}{π} \int_{0}^{\infty} {(\frac{sin x}{x})}^{n} cos (b x) d x$ , Math. Comp. 19 (1965) 113–117.
A. Schinzel, A Property of Polynomials with an Application to Siegel's Lemma, Monatsh. Math. 137 (2002) 239–251.
G. Pólya, Berechnung eines Bestimmten Integrals, Math. Ann. 74 (1913) 204–212.
N. J. A. Sloane, Sequences A049330 and A049331 in The On-Line Encyclopedia of Integer Sequences, http://www.research.att.com/ njas/sequences/.