Peter Borwein has long been involved with research on polynomials in number theory and analysis, in particular, on polynomials with restricted coefficients and prescribed factors. However, some of his earliest work treated some problems in combinatorial geometry involving arrangements of lines and points in the plane. We describe a sampling of his work in these fields, first in geometry, then on polynomials, and then we describe a problem that brings together both of these interests: For a fixed positive integer n, how many different convex polygons with n sides and unit diameter have maximal perimeter? This problem, which dates to a question of Karl Reinhardt in 1922, can be recast as a problem about polynomials with restricted coefficients and prescribed vanishing. We describe this connection, and discuss some recent results obtained both on this problem and on related questions.
A result of Karl Reinhardt from 1922 establishes that the maximal perimeter of a convex polygon with n sides and unit diameter is 2n sin(þ/2n), provided that n is not a power of 2. For a given positive integer n, how many different qualifying n-gons achieve this bound? This is unknown in general. We describe some recent progress on this problem, obtained using number theory, combinatorics, and some computation, and we provide some partial answers, including a new general lower bound.
Starting with a positive integer x, consider the iteration that sends x to ceiling(4x/3) if x is not equivalent to 1 mod 3 and halts if x is equivalent to 1 mod 3. For example, beginning with x = 15 we compute 15, 20, 27, 36, 48, 64, halt. Does this iteration halt on all initial inputs? This problem is related to the question of the existence of the so-called Z-numbers studied by Mahler and others. For the case of 4/3, this problem asks if there exists a positive real number z such that the fractional part of z(4/3)n lies in [0,1/3) for every n ≥ 1. We consider these questions for certain rational numbers p/q with q < p < q2, and describe some algorithms developed to search for Z-numbers, or, alternatively, for initial values x for which a corresponding iteration never halts. For example, in the case where p/q = 4/3, we find that a Z-number, if it exists, must exceed 1032. This is joint work with Arturus Dubickas.
Let λ(k) denote the Liouville lambda function, the completely multiplicative function defined by λ(p) = -1 for every prime p. In 1919, Polya noted that the Riemann hypothesis follows if the sum L(n) = ∑1≤k≤nλ(k) does not change sign for large n, and in 1948 Turan noted a similar property for the function T(n) = ∑1≤k≤nλ(k)/k. In 1958, Haselgrove proved that both L(n) and T(n) change sign infinitely often, without determining any precise values where a sign change occurs. In 1960, Lehman found an integer n0 > 1 where L(n0) > 0, but no specific integer n1 had been found where T(n1) < 0. We describe a recent large computation that has determined the smallest such integer.
There are a number of problems in number theory where one can be led to a false conjecture by examining only numerical data, since the smallest counterexample is so large. We describe a few such problems, then discuss some recent research that has determined the smallest counterexample in a problem involving the Liouville function. This problem dates to some work of Turan from 60 years ago. Computing this example required more than two years of CPU time. Examples like this provide for interesting discussion in an undergraduate number theory class, or in a course introducing proofs.
What is the maximal area of a convex polygon having unit diameter and a fixed number of sides n? What is the maximal perimeter of such a polygon? It is known that the regular polygon is not optimal in either problem when n is even and n ≥ 6. In fact, the area problem is unsolved when n = 2m and m ≥ 5, and the perimeter problem is open when n = 2m and m ≥ 4. We describe how an experimental approach, combining numeric and symbolic computations, led to the construction of two families of polygons, one achieving areas that are in a precise sense very nearly optimal in the open cases of the first problem, and the other exhibiting perimeters that are very nearly optimal in the open cases of the second.
We describe some asymptotic formulas for the mean value of the normalized Mahler measure for several classes of polynomials, including the unimodular polynomials and the Littlewood polynomials. We also describe mean values for the normalized Lp norms of these polynomials. This is joint work with Stephen Choi.
Suppose you need to design a $1 coin with a polygonal shape, fixed diameter, and maximal area or maximal perimeter. Are regular polygons optimal? Does the answer depend on the number of sides? We investigate these two extremal problems for polygons, and show how to construct polygons that are optimal, or very nearly so, in each case.
We describe some conjectures of Pólya and Turán related to the Riemann hypothesis, an important problem in number theory that concerns the distribution of prime numbers. Both conjectures are now known to be false, but it is of some interest to compute some explicit counterexamples. Some are known in the problem of Pólya, but none is known in the problem of Turán. We describe some algorithms for investigating these problems, and indicate how some answers may be in reach by using some parallel computation.
Suppose you need to design a $1 coin with a polygonal shape, fixed diameter, and maximal area or maximal perimeter. Are regular polygons optimal? Does the answer depend on the number of sides? With the aid of a computer algebra system, we investigate these two extremal problems for polygons, and show how to construct polygons that are optimal, or very nearly so, in almost every case.
Gonçalves' inequality relates Mahler's measure of a univariate polynomial to its L2 norm. If F(z) = Σn=0N an zn is a polynomial of positive degree with complex coefficients, then this inequality states that ||F||22 ≥ M(F)2 + |a0 aN|^2/M(F)2. We establish some generalizations of this inequality for other Lp norms. This is joint work with P. Borwein and J. Vaaler.
John Guare's 1990 play Six Degrees of Separation made the famous speculation that each person on the planet is connected to everyone else by a chain of at most six people, where each link represents a personal acquaintance. A few years later, some college students popularized the game Six Degrees of Kevin Bacon, where one is challenged to link any actor to Bacon with a chain of length at most six, where each link represents a co-starring role in a movie. For example, Will Ferrell appeared with Tim Robbins in Anchorman, and Tim Robbins starred in Mystic River with Kevin Bacon. Can one always win at this game? (Think of some actors you'd like to try!) Is Kevin Bacon really the center of the Hollywood universe? Are there other actors that are better choices? What about other networks? We will investigate these questions using a bit of graph theory and probability, and we'll talk about some other "small world" phenomena.
A Barker sequence is a sequence a1, ..., an having the property that each ai=±1 and |Σi=1n-kai ai+k| ≤ 1 for each k>0. A longstanding conjecture asserts that no Barker sequences with length greater than 13 exist. We summarize some currently known facts on this problem, then describe some analytic problems related to this conjecture regarding polynomials whose coefficients are all ±1 (Littlewood polynomials). In connection with one such problem, by optimizing a method of D. Newman we show that the L1 norm of such a polynomial over the unit circle is bounded away from its L2 norm by a small amount, improving the standard inequality arising from Cauchy-Schwarz. With apologies to fans of This is Spinal Tap, with a bit of computation one may in fact find that this theorem goes all the way to eleven.
Gonçalves' inequality relates the L2 norm of a polynomial over the unit circle to its Mahler measure. We describe some generalizations of this inequality to other Lp norms, and determine some other lower bounds on the Lp norm of a polynomial in terms of its coefficients.
In 1933, D. H. Lehmer asked if Mahler's measure of a polynomial with integer coefficients having at least one root off the unit circle is bounded away from 1. We resolve this problem for the case of the Littlewood polynomials, which have all their coefficients equal to ±1. In fact, we solve the problem for any polynomial with no cyclotomic factors whose coefficients are all congruent to 1 modulo a fixed integer m>=2. Similar methods allow us to resolve the related question of Schinzel and Zassenhaus on algebraic numbers for the same class of polynomials. This is joint work with P. Borwein, E. Dobrowolski, and A. Dubickas.
We discuss Lehmer's question on the existence of integer polynomials with small Mahler's measure for some special classes of polynomials, including the Littlewood polynomials, which have all ±1 coefficients. We also consider some related problems, like the conjecture of Schinzel and Zassenhaus, for these polynomials. This is joint work with P. Borwein, E. Dobrowolski, and A. Dubickas.
Lehmer asked if there exist polynomials with integer coefficients having Mahler's measure approaching 1, but not equal to 1. We resolve this problem for the special case of polynomials with no cyclotomic factors whose coefficients are all congruent to 1 modulo a fixed integer m>1. We use similar methods to determine a lower bound in the problem of Schinzel and Zassenhaus on the largest root of such a polynomial, and to improve a lower bound on the height of an algebraic unit whose minimal polynomial splits completely over a p-adic field. This is joint work with Peter Borwein, Edward Dobrowolski, and Arturas Dubickas.
Mahler's measure of a monic polynomial f(x) is the product of the absolute values of those roots of f that lie outside the unit circle. Lehmer asked if there exist polynomials with integer coefficients having Mahler's measure approaching 1, but not equal to 1. We study this problem for the special case of polynomials whose coefficients are all congruent to 1 modulo a fixed integer m>1, and consider some related problems as well.
A Littlewood polynomial of degree d has the form ±1±x±x2±···±xd-1±xd. These polynomials arise in many problems in signal processing and mathematical analysis, in questions concerning the locations or multiplicities of their roots, or especially large or especially small values of certain Lp norms, or Mahler's measure. We survey some of these problems, describe some of the methods from analysis, combinatorics, and number theory used to study them, and discuss some recent results.
The diameter of a polygon is the length of the longest line segment connecting two vertices of the polygon. What is the maximal area of an octagon with fixed diameter? Can you do better then the regular octagon, seen in a standard stop sign? (If so, should we alert the Department of Transporation?) We'll talk about these and some similar questions, and along the way we'll show how a computer algebra system can be very helpful in solving some complicated calculus questions.
We describe some results on Lehmer's question and the Schinzel-Zassenhaus problem for the special case of polynomials whose coefficients are all odd. As part of the method, we describe the construction of some auxiliary polynomials used to obtain lower bounds on problems regarding Mahler's measure.
We survey several algorithms for searching for polynomials with small Mahler's measure, discussing methods for both one-variable and two-variable polynomials. We also describe a related algorithm connected with another talk later in the conference.
Let N denote the set of polynomials whose coefficients are all 0 or 1 with constant term 1. It is easy to construct polynomials in N having repeated cyclotomic factors with arbitrarily high multiplicity. In 1993, Odlyzko and Poonen asked if there are any polynomials in N with repeated noncyclotomic factors. We describe some algorithms developed to search for polynomials in N having a prescribed factor, and report on results obtained when the required factor is a power of a noncyclotomic polynomial with small Mahler measure. The same methods allow us to search for multiples of a given polynomial in any set of polynomials where only two values are allowed as coefficients, and we describe an application searching for polynomials with ±1 coefficients and small measure.
Suppose N points are arranged in the plane, and consider the set of lines connecting two or more of these points. We say a line is ordinary if it connects exactly two of these points. If the points don't all lie on the same line, must there exist at least one ordinary line? This problem was first posed more than 100 years ago, and was publicized by the Hungarian mathematician Paul Erdos in the 1940s. We describe an unusual solution to the problem found by the computer scientist Edsger Dijkstra, and describe some results on related problems discovered by undergraduates.
It is easy to construct polynomials with {0,1} coefficients and repeated cyclotomic factors, for example, (x+1)(x3+1)(x7+1)...(x2m-1+1). In 1993, Odlyzko and Poonen asked if there exist polynomials with {0,1} coefficients and repeated noncyclotomic factors. We describe an algorithm for searching for such polynomials and exhibit several examples produced by our method.
We consider the problem of determining the volume of the intersection of the n-dimensional unit cube centered at the origin with a subspace of codimension 1. We derive an exact formula for this volume using elementary geometry, and discuss some applications of cube slicing, including an asymptotic formula for an interesting integral. We also discuss a formula for a central slice of the n-dimensional octahedron.
I discuss some of my experiences as a graduate student at the University of Texas, including finding a thesis advisor, choosing a thesis topic, and writing a thesis.
We consider three problems regarding polynomials with restricted coefficients. Each one concerns determining the minimal degree of a polynomial of a particular type having a zero of prescribed order at -1. Boyd studied this problem for the case of the Littlewood polynomials, where only 1 and -1 are permitted as coefficients; this problem arises in coding theory and engineering. We study the same problem for height 1 polynomials, where the allowed coefficients are 0, 1, and -1, and for Newman polynomials, where only 0 and 1 are permitted. The former problem arises in diophantine analysis and is connected to a conjecture of Erdos and Szekeres in analysis. The latter problem is linked to questions in combinatorics regarding integer sets with distinct subset sums and another conjecture of Erdos. We describe several algorithms developed to investigate these problems, employing lattice reduction, restrictions on subsequences of coefficients, and efficient combinatorial enumeration to determine the extremal polynomials.
Fermat's famous "last theorem" states that there are no solutions to the equation an + bn = cn in positive integers a, b, and c when n>2. Posed by Fermat more than 360 years ago, this statement was proved only recently by Andrew Wiles. The study of problems like this one belongs to a branch of mathematics called Diophantine analysis. In this talk, we will introduce this subject and the kinds of problems it treats. We will then describe what is often called the most important open problem in the subject: the abc conjecture, and talk about its relation to Fermat's last theorem and other interesting problems in Diophantine analysis. Only knowledge of calculus and familiarity with polynomials is needed.
A Newman polynomial is a univariate polynomial with all coefficients equal to 0 or 1. We study Newman polynomials having a zero of prescribed order at -1 and degree as small as possible, and determine whether a certain greedy construction produces an optimal solution. Since the product $\prod_{e\in E} (1+x^e)$ is Newman if and only if the subsets of E have distinct sums, our study leads us to consider sets of odd integers with this property, and leads us to a problem posed by Erdös.
We discuss some problems on polynomials that arise in both analytic number theory and signal processing. These problems concern polynomials with +-1 coefficients (zero is not allowed) having a certain flatness property, in that their values over the unit circle do not stray far from their L_2 mean value. We focus on two particular families of polynomials that arise in both fields: a generalization of the Rudin-Shapiro polynomials, and certain polynomials constructed using the Legendre symbol.
The knapsack cryptosystem was one of the first two public-key cryptosystems invented, along with the RSA cryptosystem. RSA remains in wide use today, but knapsack met an early demise. First proposed in 1978 by Merkle and Hellman, the knapsack cryptosystem was thought to be difficult to break because its security seemed dependent on the difficulty of a problem known to be NP-complete. In the early 1980's, Shamir and Brickell showed that this cryptosystem could be broken in polynomial time, and in 1985 Lagarias and Odlyzko showed how lattice basis reduction algorithms can often be used to crack secret messages produced by this cryptosystem very quickly.
We begin with a review of the knapsack cryptosystem and show why it seemed so promising. We then describe the LLL lattice basis reduction algorithm and the method of Lagarias and Odlyzko for breaking the code, and demonstrate their method. We conclude with some related applications of lattice basis reduction algorithms and their role in modern cryptography.
We study the minimal degree d(m) of a polynomial with height 1 and a zero of order m at 1. We compute d(m) and find all the extremal polynomials for m up to 10, and we determine upper bounds on d(m) for several additional m. The method uses algebraic number theory and combinatorial computations and relies on showing that a polynomial with height 1, bounded degree, and a zero of high order at 1 automatically vanishes at several roots of unity. Our examples bring to mind a question of Erdos and Szekeres.
Mahler's measure of a monic polynomial f(x) is defined as the product of the absolute values of the roots of f(x) that lie outside the unit disk. In 1933, D. H. Lehmer asked if it was possible to find polynomials with integer coefficients having Mahler's measure arbitrarily close to 1, but greater than 1. This problem remains open, and it has several interesting consequences. In this talk, we will summarize some known facts and recent work regarding Mahler's measure and related topics, discuss some applications in number theory and ergodic theory, and present several open problems. We will also mention some formulas recently conjectured by Boyd expressing certain limiting values of Mahler's measure in terms of values of L-functions associated with elliptic curves.
We describe a public-key cryptosystem based on the so-called "knapsack problem" and show how secret messages in this cryptosystem often can be deciphered rather quickly by an observer having no knowledge of the decryption key. This method of cracking the secret messages, first described by Lagarias and Odlyzko in 1985, employs an algorithm for finding a "reduced basis" for a lattice.
In 1985 Lagarias and Odlyzko showed how lattice basis reduction can be used to crack certain public-key cryptosystems based on the knapsack problem. We describe an implementation of their method in Maple and demonstrate how knapsack codes can be created and broken live in the classroom. This topic makes an interesting demonstration in a number theory or an advanced linear algebra class.
We demonstrate how presenting some interesting quartic surfaces helps students in multivariable calculus to refine their ideas about saddle points. This helps to motivate the study of the second derivative test.
Given a positive integer m, it is always possible to find a polynomial, all of whose coefficients are 0, +1, or -1, that is divisible by (x-1)^m. We ask two questions: What is the smallest degree among all polynomials with this property? What is the fewest number of monomials required in such a polynomial? The first question leads to a conjecture of Erdos and Szekeres, and the second question is related to an old problem in number theory on sums of powers of integers. In this talk we discuss the relationship of these questions on polynomials to these other problems and describe some algorithms designed to answer these questions.
Given a monic real polynomial with all its roots on the unit circle, we ask to what extent one can perturb its middle coefficient and still have a polynomial with all its roots on the unit circle. We show that the set of possible perturbations forms a closed interval of length at most 4, with 4 achieved only for polynomials of the form x^2n+cx^n+1 with c in [-2,2]. If we restrict to integer coefficients then the polynomials in question are products of cyclotomics, and in this case we characterize the polynomials allowing a shift of length 3. We also investigate the connection between slightly perturbed products of cyclotomic polynomials and polynomials with small Mahler measure. We describe a subexponential algorithm for searching for polynomials with small Mahler measure by perturbing products of cyclotomic polynomials and report on the polynomials found by this algorithm through degree 64.
Pick any actor or actress and try to connect him or her to Kevin Bacon through co-starring roles in movies. For example, Denzel Washington starred with Tom Hanks in Philadelphia, and Tom Hanks was in Apollo 13 with Kevin Bacon. In a popular version of this game called "Six Degrees of Kevin Bacon," one is challenged to connect any actor to Bacon using at most six links. Can this always be done? Is Kevin Bacon really the center of the Hollywood universe? Are there any other actors that are better choices? We will investigate these questions by introducing some ideas from the field of graph theory. We will also discuss some similar problems on interconnections, including networks of acquaintances.
The Mahler measure of a monic polynomial f, denoted M(f), is the absolute value of the product of those roots of f that lie outside the unit disk. Lehmer's conjecture asserts that there exists a constant c>1 such that M(f) >= c for any polynomial f with integer coefficients and f(0) != 0 that is not a product of cyclotomic polynomials. Lehmer's conjecture has many applications in number theory, and it arises in ergodic theory in problems concerning the entropy of automorphisms of higher-dimensional tori. We describe several algorithms for searching for integer polynomials with small Mahler measure and report on some recent extensive searches. Two searches extend some previous computations by D. Boyd, a third constructs slightly perturbed products of cyclotomic polynomials, and a fourth checks polynomials with a fixed number of ±1 coefficients.
Given N distinct points in the plane that do not all lie on the same line, must there exist a line that contains exactly two of the points? Sylvester posed this problem in 1893, and it remained unsolved until 1933, when Gallai proved that the answer is yes. More recently, Dijkstra presented a proof of this fact by designing an algorithm for constructing such a line. In this talk, we first discuss how one might try to answer Sylvester's question using some traditional proof techniques. We then describe the elements of an algorithmic proof and present Dijkstra's argument. Finally, we mention some interesting problems related to Sylvester's question.
We describe several algorithms for searching for polynomials with small Mahler measure and report on their implementation. Two searches extend some previous computations by D. Boyd. A third algorithm constructs slightly perturbed products of cyclotomic polynomials, and a fourth strategy checks polynomials with height one and a fixed number of nonzero coefficients. We obtain many polynomials with small Mahler measure and several new small Salem numbers. We also note some new small limit points of Mahler measures.
Let f(x) be a monic polynomial with integer coefficients. The Mahler measure of f, denoted M(f), is the product of the absolute values of the roots of f that lie outside the unit disk. So M(f) >= 1, and it turns out that it is easy to characterize the polynomials with M(f)=1. In 1933, D. H. Lehmer asked if it was possible to find a polynomial f with 1<M(f)<1+epsilon for any epsilon>0. This question remains open, and has been the subject of much study in recent years. After reviewing recent progress on Lehmer's problem and discussing some applications, I will describe several algorithms for searching for polynomials with small Mahler measure and compare their complexities. These algorithms have been implemented in C++, and I will summarize some recent results.
We describe a method of searching for polynomials with small Mahler measure. We test irreducible factors of polynomials formed by adding +-1 to some of the middle coefficients of products of cyclotomic polynomials. Most of the previously known polynomials with small measure are found using this strategy, as well as a number of new polynomials.
Last updated April 6, 2008.