Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2002 | Book

Introduction Read chapter Read first chapter

Computational Excursions in Analysis and Number Theory

Author: Peter Borwein

Publisher: Springer New York

Book Series : CMS Books in Mathematics

Included in: Professional Book Archive

Login to get access
insite
SEARCH

About this book

This book is designed for a topics course in computational number theory. It is based around a number of difficult old problems that live at the interface of analysis and number theory. Some of these problems are the following: The Integer Chebyshev Problem. Find a nonzero polynomial of degree n with integer eoeffieients that has smallest possible supremum norm on the unit interval. Littlewood's Problem. Find a polynomial of degree n with eoeffieients in the set { + 1, -I} that has smallest possible supremum norm on the unit disko The Prouhet-Tarry-Escott Problem. Find a polynomial with integer co­ effieients that is divisible by (z - l)n and has smallest possible 1 norm. (That 1 is, the sum of the absolute values of the eoeffieients is minimal.) Lehmer's Problem. Show that any monie polynomial p, p(O) i- 0, with in­ teger coefficients that is irreducible and that is not a cyclotomic polynomial has Mahler measure at least 1.1762 .... All of the above problems are at least forty years old; all are presumably very hard, certainly none are completely solved; and alllend themselves to extensive computational explorations. The techniques for tackling these problems are various and include proba­ bilistic methods, combinatorial methods, "the circle method," and Diophantine and analytic techniques. Computationally, the main tool is the LLL algorithm for finding small vectors in a lattice. The book is intended as an introduction to a diverse collection of techniques.

Table of Contents

Frontmatter
Chapter 1. Introduction
Abstract
This book focuses on a variety of old problems in number theory and analysis. The problems concern polynomials with integer coefficients and typically ask something about the size of the polynomial with an appropriate measure of size and often with some restriction on the height and the degree.
Peter Borwein
Chapter 2. LLL and PSLQ
Abstract
The single most useful algorithm of computational number theory is the LLL lattice basis reduction algorithm of Lenstra, Lenstra, and Lovász [1982]. It finds a relatively short vector in an integer lattice. In this chapter we give some examples of how LLL can be used to approach some of the central problems of the book. Appendix B deals, in detail, with the LLL algorithm and the closely related PSLQ algorithm for finding integer relations. In many of our applications LLL can be treated as a “black box”—why it works doesn’t matter. One inputs a lattice and receives as output a candidate short vector that can be verified to have the requisite properties for the particular problem under consideration.
Peter Borwein
Chapter 3. Pisot and Salem Numbers
Abstract
There are two very special classes of algebraic integers that arise repeatedly and naturally in this area of study. Recall that an algebraic integer is any root of any monic polynomial with integer coefficients. A real algebraic integer α is a Pisot number if all its conjugate roots have modulus strictly less than 1. A real algebraic integer α is a Salem number if all its conjugate roots have modulus at most 1, and at least one (and hence (see E2) all but one) of the conjugate roots has modulus exactly 1. As is traditional, though somewhat confusing, we denote the class of all Pisot numbers by S and the class of all Salem numbers by T.
Peter Borwein
Chapter 4. Rudin—Shapiro Polynomials
Abstract
Littlewood’s problem asks how small a polynomial with coefficients from the set {+1, -1} can be on the unit disk.
Peter Borwein
Chapter 5. Fekete Polynomials
Abstract
The Fekete polynomials are defined, for prime p, by
$$ {f_p}(z): = \sum\limits_{{k = 1}}^{{p - 1}} {\left( {\frac{k}{p}} \right){z^k}} $$
where (\( \left( {\frac{ \cdot }{p}} \right) \)) is the Legendre symbol. Recall that the Legendre symbol (\( \left( {\frac{k}{p}} \right) \)) is defined as follows:
$$ \left( {\frac{k}{p}} \right): = \left\{ {\begin{array}{*{20}{c}} 1 {if\,{x^2} \equiv k\;(\bmod p)\,has\,a\,nonzero\,solution,} {} \\ 0 {if\,p\,divides\,k,} {} \\ { - 1} {otherwise.} {} \\ \end{array} } \right. $$
Peter Borwein
Chapter 6. Products of Cyclotomic Polynomials
Abstract
As in Chapter 3, the nth cyclotomic polynomial Φ n is the minimal polynomial of a primitive nth root of unity. Recall that Φ n is given by
$$ {\Phi_n}(z) = \prod\limits_{{\begin{array}{*{20}{c}} {1 \leqslant j \leqslant n} \\ {\gcd \left( {j,n} \right) = 1} \\ \end{array} }} {\left( {z - \exp \left( {{{{j2\pi i}} \left/ {n} \right.}} \right)} \right)} $$
.
Peter Borwein
Chapter 7. Location of Zeros
Abstract
We are interested in the zeros of polynomials with restricted coefficients. A typical restriction is that the first coefficient dominates the other coefficients— as is the case in <Emphasis FontCategory=“NonProportional”>Fn</Emphasis>, <Emphasis FontCategory=“NonProportional”>Ln</Emphasis>, and <Emphasis FontCategory=“NonProportional”>An</Emphasis>. However, none of the results of this section are about polynomials with integer coefficients specifically.
Peter Borwein
Chapter 8. Maximal Vanishing
Abstract
The location of the zeros of Littlewood polynomials and related classes of low-height polynomials is subtle and interesting. The zeros cluster heavily around the unit circle and appear to form a set with fractal boundary.
Peter Borwein
Chapter 9. Diophantine Approximation of Zeros
Abstract
Detail around 1 of zeros of all degree 15 polynomials with {+1, -1} coefficients.
Peter Borwein
10. The Integer Chebyshev Problem
Abstract
The main problem of this chapter is to find a polynomial in <Emphasis FontCategory=“NonProportional”>Z</Emphasis> n of minimal supremum norm on an interval. This is P1, and it is of a slightly different flavour than most of the other problems in this book, in that there is no restriction on the size of the coefficients. We now state P1 with greater precision.
Peter Borwein
11. The Prouhet—Tarry—Escott Problem
Abstract
A classical problem in Diophantine equations that occurs in many guises is the Prouhet-Tarry-Escott problem. This is the problem of finding two distinct lists (repeats are allowed) of integers [α 1,…,α n] and [β 1 ,…,β n] such that
$$ \begin{array}{l} {\alpha _1} + \cdots + {\alpha _n} = {\beta _1} + \cdots + {\beta _n} \\ \alpha _1^2 + \cdots + \alpha _n^2 = \beta _1^2 + \cdots + \beta _n^2 \\ \;{\kern 1pt} \;\;\;\;\;\;\;\;\;\; \vdots \;\;\;\;\;\;\; \vdots \quad \quad \vdots \\ \alpha _1^2 + \cdots + \alpha _n^2 = \beta _1^2 + \cdots + \beta _n^2 \\ \end{array} $$
We will call this the Prouhet-Tarry-Escott Problem. We call n the size of the solution and k the degree. We abbreviate the above system by writing \( \left[ {{\alpha_i}} \right]\,{ =_k}\,\left[ {{\beta_i}} \right]. \)
Peter Borwein
Chapter 12. The Easier Waring Problem
Abstract
Wright [1934] stated, and probably misnamed, the following variation of the well-known Waring problem concerning writing integers as sums of kth powers. The problem is to find the least n such that for all m there are natural numbers [α 1,…,αn] with
$$ \pm \alpha_1^k\pm \cdots \pm \alpha_1^k = m $$
for some choice of signs. We denote the least such n by v(k). Recall that the usual Waring problem requires all positive signs. For arbitrary k the best known bounds for v(k) derive from the bounds for the usual Waring problem. This gives the bound v(k) ≪ klog(k) (though it is believed that the “right” bound in both the usual Waring problem and the easier Waring problem is 0(k)). So to date, the “easier” Waring problem is not easier than the Waring problem. However, the best bounds for small k are derived in an elementary manner from solutions to the Prouhet-Tarry-Escott problem. This is discussed later in this chapter.
Peter Borwein
Chapter 13. The Erdős—Szekeres Problem
Abstract
One approach to the Prouhet-Tarry-Escott problem is to construct products of the form
$$ p(z): = \prod\limits_{{k = 1}}^N {\left( {1 - {z^{{{\alpha_i}}}}} \right)} $$
. This product has a zero of order N at 1, and the idea is to try to minimize the length (the l 1 norm) of p. We denote by E N * the minimum possible l 1 norm of any TV-term product of the above form. The l 1 norm is just the sum of the absolute values of the coefficients of the polynomial p when it is expanded, and an ideal solution of the Prouhet-Tarry-Escott problem arises when E N * = 2N (as in Theorem 1(c) of Chapter 11).
Peter Borwein
Chapter 14. Barker Polynomials and Golay Pairs
Abstract
Both Barker polynomials (which probably exist only for a few small degrees) and Golay complementary pairs are combinatorial objects that, as discussed later, have certain optimal properties in signal processing and signal recovery. They also provide, when they exist, extremal examples for various problems we are considering in this book.
Peter Borwein
Chapter 15. The Littlewood Problem
Abstract
The Littlewood problem concerns the size of the L p norm on the boundary of D of Littlewood polynomials. When p > 2 it asks how small the L p norm can be, and when p 〈 2 it asks how large the L p norm can be. In both cases we are interested in how close these norms can be to the L2 norm. Recall that the L 2 norm of a Littlewood polynomial of degree n is \( \sqrt {{n + 1}} \) That the behaviour changes at p = 2 is expected from Hölder’s inequality, which gives, for 1 ≤ α 〈 β ≤ 00 and α -1 + β -1 = 1, that
$$ \begin{gathered} \left\| P \right\|_2^2\, \leqslant \,{\left\| P \right\|_{\alpha }}\,{\left\| P \right\|_{\beta }} \hfill \\ \hfill \\ \end{gathered} $$
Peter Borwein
Chapter 16. Spectra
Abstract
In this chapter, we examine spectra, the sets of values which result when various classes of polynomials are evaluated at a fixed number q. When this class is <Emphasis FontCategory=“NonProportional”>F</Emphasis> and q is a Pisot number, the spectrum
$$ \left\{ {p(q):p \in \mathcal{F}} \right\} $$
is, quite surprisingly, discrete. Indeed, from El of Chapter 3, we have that for q a Pisot number and p ∈ <Emphasis FontCategory=“NonProportional”>Z</Emphasis> of height h with q not a root of p,
$$ \left| {p(q)} \right| \geqslant c\left( {q,h} \right) $$
where the positive constant c(q, h) depends only on q and h. This suggests the question of establishing the exact value for c(q,h). Specifically, we search for the minimum positive value in the spectrum of height h polynomials evaluated at a number q, where q is between 1 and 2.
Peter Borwein
Backmatter
Metadata
Title
Computational Excursions in Analysis and Number Theory
Author
Peter Borwein
Copyright Year
2002
Publisher
Springer New York
Electronic ISBN
978-0-387-21652-2
Print ISBN
978-1-4419-3000-2
DOI
https://doi.org/10.1007/978-0-387-21652-2