A Barker sequence is a finite sequence of integers, each ±1, whose off-peak aperiodic autocorrelations are all at most 1 in absolute value. Very few Barker sequences are known, and it has long been conjectured that no additional ones exist. Many arithmetic restrictions have been established that severely limit the allowable lengths of Barker sequences, so severely that no permissible lengths were even known. Using computational resources of Compute Canada, we identify the smallest plausible value for the length of a new Barker sequence, and we compute a number of permissible lengths up to a sizable bound. This work involves a substantial search for Wieferich prime pairs (q, p), which are defined by the property that qp−1 ≡ 1 mod p2. This is joint work with Peter Borwein.
A Reinhardt polygon is a convex n-gon that is optimal in three different geometric optimization problems: it has maximal perimeter relative to its diameter, maximal width relative to its diameter, and maximal width relative to its perimeter. Many Reinhardt polygons exhibit a particular periodic structure, and these are well understood. However, for certain values of n, such as n = 30 and n = 42, some sporadic Reinhardt polygons also occur. We characterize the integers n for which sporadic Reinhardt polygons with n sides exist, and investigate the number of such polygons, relative to the number of periodic ones with n sides. This is joint work with Kevin Hare.
A Barker sequence is a finite sequence of integers, a0, …, an−1, each ±1, whose aperiodic autocorrelations are uniformly small: for each k > 0, one requires that |Σi=0n−1−k aiai+k| ≤ 1. Very few Barker sequences are known, and it has long been conjectured that no additional ones exist. Many arithmetic restrictions have been established that severely limit the allowable lengths of Barker sequences, so severely that no permissible lengths were even known. We identify the smallest plausible value for the length of a new Barker sequence, and we compute a number of permissible lengths up to a sizable bound (Google it!).
A Barker sequence is a finite sequence of integers, each ±1, with the property that the dot product of the sequence with any nontrivial shifted version of itself is either −1, 0, or 1. For example, (1, 1, 1, −1) is a Barker sequence, since (1, 1, 1) ⋅ (1, 1, −1) = 1, (1, 1) ⋅ (1, −1) = 0, and (1) ⋅ (−1) = −1. Very few Barker sequences are known, and it has long been conjectured that no others exist. We will discuss the origins of this problem, and how it is related to some other well-studied questions in analysis and combinatorics. We will also describe some known algebraic restrictions on the possible length of a Barker sequence, and report on some substantial computations aimed at identifying some plausible values. In particular, we will show that if a new Barker sequence exists, then it must have a rather large length.
We investigate the behavior of the function Lα(x) = Σn≤x λ(n)/nα, where λ(n) is the Liouville function and α is a real parameter. The case α = 0 was investigated by Pólya; the case α = 1, by Turán. The question of the existence of sign changes in both L0(x) and L1(x) is related to the Riemann hypothesis. We investigate similar questions for Lα(x) with 0 ≤ α ≤ 1, and their connections to the Riemann hypothesis and other properties of the zeros of the Riemann zeta function. This is joint work with Timothy Trudgian.
A Newman polynomial has all its coefficients in {0, 1} and constant term 1; every root of a Newman polynomial has modulus between 1/τ and τ, where τ denotes the golden ratio. We show that every negative Pisot number in (−τ, −1) with no positive conjugates, and every negative Salem number in the same range obtained by using Salem's construction on small negative Pisot numbers, is satisfied by a Newman polynomial. We also verify this for all negative Salem numbers α > −τ having small degree. We then raise the question of whether there exists a real constant C > 1 so that if α is an algebraic unit having no positive real conjugates and Mahler's measure of α is less than C, then a Newman polynomial must exist having α as a root. We show however that one cannot possibly take C = τ in this statement by constructing a number of integer polynomials having no positive real roots and Mahler's measure less than τ, which do not divide any Newman polynomial. This is joint work with Kevin Hare.
The diameter of a compact planar set is the maximal distance between two points in the set; its width is the minimal distance between a pair of parallel lines that sandwich the set. Fix a positive integer n, and fix the value of one of four different attributes of a convex n-gon: its area, perimeter, diameter, or width. Then select another one of these attributes, and try building a convex n-gon that either maximizes or minimizes this value, relative to the fixed quantity. This produces six essentially different optimization problems for polygons, including the classical isoperimetric problem (maximizing the area for a fixed perimeter). We consider a number of these problems, and their often surprising solutions. For example, in only one of these problems is the regular n-gon always the unique optimal solution. Our investigation combines some analysis and geometry with combinatorics, number theory, and computation.
James Joseph Sylvester founded the first research school in mathematics in America more than a century ago, in fact in Maryland. We'll investigate a question in geometry first posed by Sylvester, as well as some related problems. Suppose a finite number of points are placed in the plane in such a way that they do not all lie on the same line. Must there exist a line that connects exactly two of the points? Now suppose that each of the points is colored blue or gold. Must there exist a line that joins two or more points of one color, but intersects none of the other color? Does anything change if you have an infinite number of points? We'll describe some novel methods used to investigate these problems, and discuss several interesting results, including a number of contributions made by undergraduate students.
A Reinhardt polygon is a convex n-gon that is optimal in three different geometric optimization problems, for example, it has maximal perimeter relative to its diameter. Many Reinhardt polygons exhibit a particular periodic structure, and these are well understood. However, for certain values of n, like n = 30 and n = 42, some additional sporadic Reinhardt polygons also occur. We characterize the integers n for which sporadic Reinhardt polygons with n sides exist, and obtain a lower bound on their number. The method relies on recasting the problem into a question about polynomials having prescribed vanishing and exhibiting a certain pattern in their coefficients. This is joint work with Kevin Hare.
Due to recent population shifts, the largest county in North Carolina (Mecklenburg county, which contains Charlotte) recently needed to redraw its district lines for electing county commissioners and school board members. Faced with this problem, a county advisory board published a number of desired qualities for a new districting plan, including some legal requirements and some recommended demographic attributes. It also asked that the new districts be created by using only existing voting precincts; new precincts could not be created. However, the board did not know if it was even possible to partition the 195 precincts into six districts in a way that possessed all of the desired qualities, and it solicited public input. We describe an algorithmic approach to this combinatorial optimization problem for the Charlotte metropolis, employing a method originally described by Nicholas Metropolis.
The Liouville function λ(n) is the completely multiplicative arithmetic function defined by λ(p) = −1 for each prime p. Pólya investigated the summatory function L0(x) = Σn ≤ x λ(n), and Turán studied a weighted version, L1(x) = Σn ≤ x λ(n)/n. The behavior of both of these functions is related to the Riemann hypothesis. We investigate the more general family of functions Lα(x) = Σn ≤ x λ(n)/nα with 0 ≤ α ≤ 1, and study connections between these functions, the Riemann hypothesis, and other questions concerning the zeros of the zeta function. This is joint work with Tim Trudgian.
More than 40 years ago, P. Turán asked if every integer polynomial is ‘close’ to an irreducible polynomial. More precisely, he asked if there exists an absolute constant C such that for every polynomial f in Z[x] there exists an irreducible polynomial g in Z[x] with deg(g) ≤ deg(f) and L(f − g) ≤ C, where L(·) denotes the sum of the absolute values of the coefficients. This problem remains open, and we report on some recent progress on it. By investigating the analogous question over certain finite fields, we determine that C = 5 suffices for all polynomials of degree at most 40, and we discuss how well our data fit the predictions of a heuristic model. We also show that one cannot obtain better results using the local strategy for large degrees, as we prove that a positive proportion of the polynomials in F2[x] have distance at least 4 to any irreducible polynomial in this ring. This is joint work with Michael Filaseta.
For a positive integer n that is not a power of 2, precisely the same family of convex polygons with n sides is optimal in three different extremal problems involving the perimeter, the diameter, and the width of an n-gon. For example, these shapes have maximal perimeter relative to their diameter. We investigate the combinatorial question of determining the number of different convex n-gons E(n) that are optimal in these isodiametric and isoperimetric problems. We first study the extremal polygons that exhibit a particular periodic structure, and then turn to the question of the existence of sporadic extremal shapes, which appear to occur only for certain values of n. We obtain a lower bound on E(n) that depends on the factorization of n, and prove that it is an exact formula in certain cases. We also show that these geometric questions can be recast as problems about sums of certain roots of unity, and present some open problems.
How large can one make the perimeter of a convex polygon, if the number of sides is fixed, as well as the maximum distance between a pair of its vertices? It may surprise you that the regular polygon is often not the best shape! Reinhardt answered this question in 1922, and provided a means for characterizing the extremal polygons in almost every case. However, the problem of determining the number of optimal polygons with a given number of sides remained open for a long time. We discuss this problem, and show that there are usually exponentially many different optimal shapes, even after taking symmetry into account. We also provide some bounds on the number of optimal polygons, and find exact formulas in certain cases. As a bonus, the family we study is optimal in two other extremal problems for convex polygons involving the width, the diameter, and the perimeter.
Ever heard that any two people on earth can be connected using a chain of at most six personal acquaintances, or that any movie star can be linked to Kevin Bacon in just six steps? See some of the mathematics behind these "six degree" phenomena!
Imagine the MAA has mandated that the serving plates used at any state dinner be polygonal in shape, in order to promote some forthcoming events in geometry at the Carriage House. Legal counsel strongly recommends convex shapes, to avoid sharp ceramic corners and hot gravy spills. As organizer, you find that various parties have strong and often conflicting priorities on the shape of the plate selected. Hungry diners prefer a dinner plate with large area, to accommodate spacious buffets. Finicky eaters prefer a dish with large perimeter, to provide more edge room for quarantining unwanted morsels. Fastidious planners balk at a plate with too large a diameter, since a certain number of diners need to be seated at each table. And efficient kitchen staffers need to ensure that the plates fit in the dishwashing machines in at least one orientation, so this constrains the width of the plate. You are faced then with a number of optimization problems. Fix the number of sides, n, of a convex polygon, and fix the value of one of the four quantities area, perimeter, diameter, or width. Then select another one of these quantities to either maximize or minimize. This produces six nontrivial problems in dinnerware design. We will discuss a number of these problems, and their often surprising solutions. For example, in only one of these six questions does the regular n-gon always provide the answer, and in several of these problems there is often more than one optimal solution.
Ever heard the old adage that you can connect any two people on the planet with a chain of at most six personal acquaintances? This notion of "six degrees of separation" has its origins in a famous psychology experiment of the late 1960s, but it occurs frequently now in popular culture. For example, you may have heard of a similar notion for actors, where the claim is that any actor can be linked to Kevin Bacon in at most six steps, with each step representing a pair of costars in the same movie. We will approach problems like these from a mathematical perspective, introducing some notions from the field of graph theory to analyze them, and we will describe a number of different six-degree phenomena. But in the meantime, do you think Kevin Bacon is really the center of the actor's universe? Can you think of an actor that you think would be really difficult to link to Kevin Bacon?
Ever heard the old adage that you can connect any two people on the planet with a chain of at most six personal acquaintances? This notion of "six degrees of separation" has its origins in a famous psychology experiment of the late 1960s, but it occurs frequently now in popular culture. For example, you may have heard of a similar notion for actors, where the claim is that any actor can be linked to Kevin Bacon in at most six steps, with each step representing a pair of costars in the same movie. We will approach problems like these from a mathematical perspective, introducing some notions from the field of graph theory to analyze them, and we will describe a number of different six-degree phenomena. But in the meantime, do you think Kevin Bacon is really the center of the actor's universe? Can you think of an actor that you think would be really difficult to link to Kevin Bacon?
For a positive integer n that is not a power of 2, precisely the same family of convex polygons with n sides is optimal in three different geometric problems. These polygons have maximal perimeter relative to their diameter, maximal width relative to their diameter, and maximal width relative to their perimeter. We study the number of different convex n-gons E(n) which are extremal in these three isodiametric and isoperimetric problems. We show that E(n) > (p/4n) · 2n/p if p is the smallest odd prime divisor of n, prove that E(n) = 1 if and only if n = p or n = 2p for some odd prime p, and compute the exact value of E(n) in several cases.
More than 40 years ago, P. Turán asked if every integer polynomial is "close" to an irreducible polynomial. More precisely, he asked if there exists an absolute constant C such that for every polynomial f in Z[x] there exists an irreducible polynomial g in Z[x] with deg(g) ≤ deg(f) and L(f − g) ≤ C, where L(·) denotes the sum of the absolute values of the coefficients. This problem remains open. We show that C = 5 suffices for all polynomials with degree at most 40 by using a computational strategy, and discuss how well our results fit the predictions of a heuristic model. This is joint work with Michael Filaseta.
More than 40 years ago, P. Turán asked if every integer polynomial is "close" to an irreducible polynomial. More precisely, he asked if there exists an absolute constant C such that for every polynomial f in Z[x] there exists an irreducible polynomial g in Z[x] with deg(g) ≤ deg(f) and L(f − g) ≤ C, where L(·) denotes the sum of the absolute values of the coefficients. This problem remains open. We show that C = 5 suffices for all polynomials with degree at most 40 by using a computational strategy, and discuss how well our results fit the predictions of a heuristic model. This is joint work with Michael Filaseta.
Suppose a finite number of points are placed in the plane in such a way that they do not all lie on the same line. Must there always be at least one line that connects exactly two of the points? What if you start with an infinite number of points? We'll investigate these questions and some related ones involving arrangements of points and lines in the plane, which date to problems posed more than a century ago by the British mathematician, James Joseph Sylvester.
The Mahler measure of an algebraic number α is the product of the absolute values of those conjugates of α that lie outside the unit disk, multiplied by the leading coefficient of its minimal polynomial. Lehmer's problem asks if the Mahler measure of α is bounded away from 1, provided α ≠ 0 and α is not a root of unity. While this problem remains open, it has been resolved in some special cases. We briefly survey some of these cases, and then describe some recent improvements in bounds on the measure in some of them. In particular, we describe improved bounds on the measure when all the coefficients of the minimal polynomial of α are congruent to 1 mod m, for a fixed integer m ≥ 2, and report on some refinements when α lies in an abelian extension of the rationals. This is joint work with J. Garza, M. Ishak, C. Pinner, and B. Wiles.
More than 40 years ago, Turán asked if every integer polynomial is "close" to an irreducible polynomial. More precisely, he asked if there exists an absolute constant C such that for every polynomial f in Z[x] there exists an irreducible polynomial g in Z[x] with deg(g) ≤ deg(f) and L(f − g) ≤ C, where L(·) denotes the sum of the absolute values of the coefficients. This problem remains unsolved. We describe some algorithms used to investigate this question, and show in particular that C = 4 suffices for monic polynomials with degree less than 35. We also describe how well our results fit the predictions of a heuristic model.
A Barker sequence is a finite sequence of integers {ai}, each ±1, for which every sum Σi aiai+k with k ≠ 0 is −1, 0, or 1. It is unknown if any Barker sequences exist with length n > 13, although a number of necessary conditions on their existence have been established, so restrictive in fact that no value of n > 13 was even known that satisfied all of the requirements. We describe a large computational investigation that significantly improves the best known lower bound on the length of a long Barker sequence. The computation involves a large search for Wieferich prime pairs (q, p), which are defined by the property that qp−1 = 1 mod p2. We also describe some connections with other open problems in number theory, combinatorics, and analysis.
Given an integer polynomial f(x), how many coefficients do you need to adjust before you are assured of finding an irreducible polynomial of the same degree or smaller? More precisely, does there exist an absolute constant C so that for every f(x) in Z[x] there exists an irreducible g(x) in Z[x] with deg(g) ≤ deg(f) and L(f − g) ≤ C, where L(h) denotes the sum of the absolute values of the coefficients of h(x)? This question was first posed by Turán in 1962, and it remains unsolved. We discuss some algorithms designed to investigate this question, and report on the results of some recent computations.
A Barker sequence is a finite sequence of integers {ai}, each ±1, for which every sum ∑i ai ai+k with k ≠ 0 is −1, 0, or 1. It is unknown if any Barker sequences exist with length n > 13, although a number of necessary conditions on their existence have been established, so restrictive in fact that no value of n > 13 was even known that satisfied all of the requirements. We describe a large computational investigation that significantly improves the best known lower bound on the length of a long Barker sequence. The computation involves a large search for Wieferich prime pairs (q, p), which are defined by the property that qp−1 = 1 mod p2. We also describe some connections between these quantities and some problems of Erdös in number theory and analysis.
A Barker sequence is a finite sequence of integers, each ±1, whose off-peak aperiodic autocorrelations are all 0, 1, or −1. No Barker sequences with length n > 13 are known, and it is widely conjectured that no long Barker sequences exist. We describe how an extensive search for Wieferich prime pairs (q, p), which are defined by the property that qp−1 = 1 mod p2 allows one to show that if a Barker sequence of length n > 13 exists, then n must be quite large.
The maximal perimeter of a convex polygon having unit diameter and a fixed number of sides n is achieved only by certain equilateral polygons, provided that n has an odd prime divisor. Some prior work of the author and others considered the problem of constructing polygons with large perimeter when n is a power of 2. We describe how an experimental approach, combining numeric and symbolic computations, was employed in some recent investigations of two related problems about polygons. The first considers the construction of equilateral convex polygons with unit diameter, 2m sides, and large perimeter. The second investigates the combinatorial problem of determining the number of essentially different polygons that exhibit the optimal perimeter for any fixed n.
A Barker sequence is a finite sequence of integers a0, ..., an−1, each ±1, for which |Σj ajaj+k| ≤ 1 for k ≠ 0. It is widely conjectured that no Barker sequences exist with length n > 13. A number of quite restrictive conditions are known on the length n of a long Barker sequence, so restrictive in fact that no permissible value of n > 13 was even known, though prior work had established that n > 1022. We describe a large computational effort aimed at identifying the smallest permissible values of n. Much of the computation consists of an extensive search for certain prime pairs (q, p) that satisfy a Wieferich condition, where qp−1 ≡ 1 mod p2.
Among convex polygons with unit diameter and a fixed number of sides n, the regular n-gon achieves neither the maximal area nor the maximal perimeter when n > 4 is even. We describe how to construct better polygons in both problems, and discuss some recent work on counting the number of different convex n-gons with unit diameter that achieve the optimal perimeter.
Suppose a finite number of points are placed in the plane in such a way that they do not all lie on the same line. Must there exist a line that connects exactly two of the points? Suppose each of the points are then colored red or blue in some way. Must there exist a line that joins two or more points of one color, but intersects none of the other color? Can you always join exactly two points of one color and none of the other? Does anything change if you have an infinite number of points? We'll investigate these questions, some of which were raised more than a century ago by the British mathematician James Joseph Sylvester. We'll describe some novel methods used to investigate these problems, and discuss several interesting results, including some contributions made by undergraduate students.
What is the maximal area of a polygon with unit diameter and a fixed number of sides? What is the maximal perimeter of such a polygon, assuming it is convex? Does the regular polygon suffice for either question? Is the solution unique? Will this abstract contain a declarative statement? We will describe some work on these problems, which date to some work of Karl Reinhardt in the early 1920s, and we will focus in particular on one combinatorial question: How many essentially distinct convex polygons with unit diameter and a fixed number of sides exhibit the maximal perimeter?
A Barker sequence is a finite sequence of integers a0, ..., an−1, each ±1, for which |Σj aj aj+k| ≤ 1 for k ≠ 0. It has long been conjectured that long Barker sequences do not exist. We describe some recent work connecting this problem to several open questions posed by Littlewood, Mahler, Erdös, Newman, Golay, and others about the existence of polynomials with ±1 coefficients that are "flat" in some sense over the unit circle. If time permits, we will also describe some recent related work concerning Lp norms and Mahler's measure for certain families of polynomials.
A Barker sequence is a finite sequence of integers a0, ..., an−1, each ±1, for which |Σj aj aj+k| ≤ 1 for k ≠ 0. It has long been conjectured that no Barker sequences exist with length n >13. We describe some recent work connecting this problem to several open questions posed by Littlewood, Mahler, Erdös, Newman, Golay, and others about the existence of polynomials with ±1 coefficients that are "flat" in some sense over the unit circle. We will also briefly describe some recent related work concerning Lp norms and Mahler's measure of polynomials. This is joint work with Peter Borwein, Erich Kaltofen, and others.
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 Transportation?) 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. Slides are available at the conference site.
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. Slides are available at the conference site, and at my site on Lehmer's Problem.
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 Erdös 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.
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. For example, the polynomial (x+1)(x3+1)(x7+1)···(x2m−1+1) has (x+1)m as a factor. In 1993, Odlyzko and Poonen asked if there exist polynomials in this set with repeated noncyclotomic factors. We describe some algorithms for searching for polynomials in N with prescribed noncyclotomic factors, and provide an answer to this question using polynomials that are in a sense very nearly cyclotomic. We also consider similar problems regarding polynomials with coefficients lying in the fixed sets {−1,1} or {−1,0,1} and their connections with a conjecture of Lehmer regarding polynomials with small Mahler measure.
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 Erdös and Szekeres in analysis. The latter problem is linked to questions in combinatorics regarding integer sets with distinct subset sums and another conjecture of Erdös. 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 Πe∈E (1+xe) 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 L2 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.
Pick any actor or actress and try to connect him or her to Kevin Bacon through co-starring roles in movies. For example, Matt Damon appeared with Tom Hanks in "Saving Private Ryan," and Tom Hanks starred 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 a similar problem regarding networks of personal acquaintances.
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 Erdös 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 x2n + cxn + 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+ε for any ε > 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 26, 2013.
