Words, words, words

Papers

Claudius. My words fly up, my thoughts remain below. Words without thoughts never to heaven go.

• An explicit approach to Hypothesis H for polynomials over finite fields [PDF]
  The anatomy of integers. Proceedings of a conference on the anatomy of integers, Montreal, March 13th-17th, 2006 eds: J.M. de Koninck, A. Granville and F. Luca, pp. 259--273 [show abstract]

  Schinzel's Hypothesis H predicts that a family of irreducible polynomials over the integers satisfying certain necessary local conditions simultaneously assumes prime values infinitely often. Here we consider an analogue of Hypothesis H for one-variable polynomials over the q-element finite field F_q and show that it holds whenever q is large compared to the degree of the product of the polynomials involved. We also show that for fixed q, the conclusion of our Hypothesis H holds for "almost all" single-polynomial families. Along the way we propose a new polynomial analogue of the Hardy-Littlewood/Bateman-Horn conjectures.

  Hide this content.

• On a conjecture of Beard, O'Connell and West concerning perfect polynomials (w/ L. Gallardo and O. Rahavandrainy) [PDF]
  Finite Fields and their Applications 14 (2008), no. 1, 242--249 [show abstract]

  Following Beard, O'Connell and West (1977) we call a polynomial over a finite field F_q perfect if it coincides with the sum of its monic divisors. The study of perfect polynomials was initiated in 1941 by Carlitz's doctoral student Canaday in the case q = 2, who proposed the still unresolved conjecture that every perfect polynomial over F₂ has a root in F₂. Beard, et al. later proposed the analogous hypothesis for all finite fields. Counterexamples to this general conjecture were found by Link (in the cases q = 11, 17) and Gallardo & Rahavandrainy (in the case q = 4). Here we show that the Beard-O'Connell-West conjecture fails in all cases except possibly when q is prime. When q = p is prime, utilizing a construction of Link we exhibit a counterexample whenever p== 11 or 17 (mod 24). On the basis of a polynomial analog of Schinzel's Hypothesis H, we argue that if there is a single perfect polynomial over the finite field F_q with no linear factor, then there are infinitely many. Lastly, we prove without any hypothesis that there are infinitely many perfect polynomials over F₁₁ with no linear factor.

  Hide this content.

• Simultaneous prime specializations of polynomials over finite fields [PDF]
  Proc. London Math. Soc. 97 (2008), no. 3, 545--567 [show abstract]

  Recently the author proposed a uniform analogue of the Bateman-Horn conjectures for polynomials with coefficients from a finite field (i.e., for polynomials in F_q[T] rather than Z[T]). Here we use an explicit form of the Chebotarev density theorem over function fields to prove this conjecture in particular ranges of the parameters. We give some applications including the solution of a problem posed by C. Hall.

  Hide this content.

• A polynomial analogue of the twin prime conjecture [PDF]
  Proc. Amer. Math. Soc. 136 (2008), no. 11, 3775--3784 [show abstract]

  We consider the problem of counting the number of (not necessarily monic) `twin prime pairs' P, P + M in F_q[T] of degree n, where M is a polynomial of degree < n. We formulate an asymptotic prediction for the number of such pairs as qⁿ goes to infinity and then prove an explicit estimate confirming the conjecture in those cases where q is large compared with n². When M has degree n-1, our theorem implies the validity of a result conditionally proved by Hayes in 1963. When M has degree zero, our theorem refines a result of Effinger, Hicks & Mullen.

  Hide this content.

• Arithmetic properties of polynomial specializations over finite fields [PDF]
  Acta Arith. 136 (2009), no. 1, 57--79 [show abstract]

  We present applications of some recent results that establish a partial finite field analogue of Schinzel's Hypothesis H. For example, we prove that the distribution of gaps between degree n prime polynomials over F_p is close to Poisson for p large compared to n. We also estimate the number of polynomial substitutions without prime factors of large degree ("smooth" polynomial substitutions); this confirms a finite field analogue of a conjecture of Martin in certain ranges of the parameters. Other topics considered include an analogue of Brun's constant for polynomials and "smooth" values of neighboring polynomials.

  Hide this content.

• On the distribution of sociable numbers (w/ M. Kobayashi and C. Pomerance) [PDF]
  J. Number Theory 129 (2009), no. 8, 1990--2009 [show abstract]

  For a positive integer n, define s(n) as the sum of the proper divisors of n. If s(n) > 0, define s₂(n) = s(s(n)), and so on for higher iterates. Sociable numbers are those n with s_k(n) = n for some k, the least such k being the order of n. Such numbers have been of interest since antiquity, when order-1 sociables (perfect numbers) and order-2 sociables (amicable numbers) were studied. In this paper we make progress towards the conjecture that the sociable numbers have asymptotic density 0. We show that the number of sociable numbers in [1, x], whose cycle contains at most k numbers greater than x, is o(x) for each fixed k. In particular, the number of sociable numbers whose cycle is contained entirely in [1, x] is o(x), as is the number of sociable numbers in [1, x] with order at most k. We also prove that but for a set of sociable numbers of asymptotic density 0, all sociable numbers are contained within the set of odd abundant numbers, which has asymptotic density about 1/500.

  Hide this content.

• A remark on sociable numbers of odd order [PDF]
  J. Number Theory 130 (2010), no. 8, 1732--1736 [show abstract]

  Write s(n) for the sum of the proper divisors of the natural number n. We call n sociable if the sequence n, s(n), s(s(n)), … is purely periodic; the period is then called the order of sociability of n. The ancients initiated the study of order-1 sociables (perfect numbers) and order-2 sociables (amicable numbers), and investigations into higher-order sociable numbers began at the end of the 19th century We show that if k is odd and fixed, then the number of sociable n ≤ x of order k is bounded by x/(log x)^1+o(1) as x goes to infinity. This improves on the previously best-known bound of x/(log log x)^1/2+o(1), due to Kobayashi, Pollack, and Pomerance.

  Hide this content.

• Revisiting Gauss's analogue of the prime number theorem for polynomials over a finite field [PDF]
  Finite Fields and their Applications 16 (2010), no. 4, 290--299 [show abstract]

  In 1901, von Koch showed that the Riemann Hypothesis is equivalent to the assertion that π(x) = Li(x) + O(x^1/2 log x). We describe an analogue of von Koch's result for polynomials over a finite prime field F_p: For each natural number n, write n in base p, say n = a₀ + a₁ p + … + a_k p^k; and associate to n the polynomial a₀ + a₁T + … + a_kT^k in F_p[T]. We let π_p(X) denote the number of irreducible polynomials encoded by integers n < X, and prove a formula for π_p(X) valid with an error term analogous to that in von Koch's theorem. Our result is unconditional, and is grounded in Weil's Riemann Hypothesis for function fields. We also investigate an asymptotic expansion for π_p(X).

  Hide this content.

• On polynomial rings with a Goldbach property [PDF]
  American Math. Monthly 118 (2011), no. 1, 71--77 [show abstract]

  David Hayes observed in 1965 that when R = Z, every element of R[T] of degree n ≥ 1 is a sum of two irreducibles in R[T] of degree n. We show that this result continues to hold for any Noetherian domain R with infinitely many maximal ideals.

  Hide this content.

• On Dickson's theorem concerning odd perfect numbers [PDF]
  American Math. Monthly 118 (2011), no. 2, 161--164 [show abstract]

  A 1913 theorem of Dickson asserts that for each fixed natural number k, there are only finitely many odd perfect numbers N with at most k distinct prime factors. We show that the number of such N is bounded by 4^k2.

  Hide this content.

• Multiperfect numbers with identical digits (w/ F. Luca) [PDF]
  J. Number Theory 131 (2011), no. 2, 260--284 [show abstract]

  Let g ≥ 2. A natural number N is called a repdigit in base g if all of the digits in its base g expansion are equal, i.e., if N = D (g^m-1)/(g-1) for some m ≥ 1 and some D in {1, 2, …, g-1}. We call N perfect if σ(N)=2N, where σ denotes the usual sum-of-divisors function. More generally, we call N multiperfect if σ(N) is a proper multiple of N. Pollack recently showed that for each fixed g ≥ 2, there are finitely many repdigit perfect numbers in base g, and that when g = 10, the only example is N = 6. We prove the same results for repdigit multiperfect numbers.

  Hide this content.

• Long gaps between deficient numbers [PDF]
  Acta Arith. 146 (2011), 33--42 [show abstract]

  Let n be a natural number. If the sum of the proper divisors of n is less than n, then n is said to be deficient. Let G(x) be the largest gap between consecutive deficient numbers belonging to the interval [1, x]. In 1935, Erdős showed that for large x, the ratio G(x)/log log log x is bounded between two positive constants. We prove that G(x)/log log log x tends to a limit as x tends to infinity. We also prove that long runs of nondeficient numbers are scarce, in that the proportion of n for which all of n+1, …, n+A are nondeficient decays triply exponentially in A.

  Hide this content.

• Hypothesis H and an impossibility theorem of Ram Murty [PDF]
  Rend. Sem. Mat. Univ. Pol. Torino 68 (2010), 183--197 [show abstract]

  Dirichlet's 1837 theorem that every coprime arithmetic progression a mod m contains infinitely many primes is often alluded to in elementary number theory courses but usually proved only in special cases (e.g., when m=3 or m=4), where the proofs parallel Euclid's argument for the existence of infinitely many primes. It is natural to wonder whether Dirichlet's theorem in its entirety can be proved by such `Euclidean' arguments. In 1912, Schur showed that one can construct an argument of this type for every progression a mod m satisfying a² ≡ 1 mod m, and in 1988 Murty showed that these are the only progressions for which such an argument can be given. Murty's proof uses some deep results from algebraic number theory (in particular the Chebotarev density theorem). Here we give a heuristic explanation for this result by showing how it follows from Bunyakovsky's conjecture on prime values of polynomials.

  We also propose a widening of Murty's definition of a Euclidean proof. With this definition, it appears difficult to classify the progressions for which such a proof exists. However, assuming Schinzel's Hypothesis H, we show that again such a proof exists only when a² ≡ 1 mod m.

  Hide this content.

• On Hilbert's solution of Waring's problem [PDF]
  Cent. Eur. J. Math. 9 (2011), no. 2, 294--301 [show abstract]

  Let k be a positive integer. In 1909, Hilbert showed that there is some integer g so that every nonnegative integer can be written as a sum of g nonnegative kth powers. Let g(k) denote the least permissible value of g for a given k. Improving on earlier work of Rieger, we show how to modify Hilbert's argument in order to obtain the explicit inequality g(k) ≤ (2k+1)^{2000 k5}.

  Hide this content.

• Powerful amicable numbers [PDF]
  Colloq. Math. 122 (2011), 103--123 [show abstract]

  Let s(n) denote the sum of the proper divisors of n. Two distinct positive integers n and m are said to form an amicable pair if s(n) = m and s(m) = n; in this case, both n and m are called amicable numbers. The first example of an amicable pair, known already to the ancients, is {220, 284}. We do not know if there are infinitely many amicable pairs. In the opposite direction, Erdős showed in 1955 that the set of amicable numbers has asymptotic density zero.

  Let l ≥ 1. A natural number n is said to be l-full if p^l divides n whenever the prime p divides n. As shown by Erdős and Szekeres in 1935, the number of l-full n ≤ x is asymptotically c_l x^1/l as x goes to infinity. Here c_l is a positive constant depending on l.

  We show that for each fixed l, the set of amicable l-full numbers has relative density zero within the set of l-full numbers.

  Hide this content.

• Values of the Euler and Carmichael functions which are sums of three squares [PDF]
  Integers 11 (2011), article A13, 16 pp. (electronic) [show abstract]

  Let φ denote Euler's totient function. The frequency with which φ(n) is a perfect square has been investigated by Banks, Friedlander, Pomerance, and Shparlinski, while the frequency with which φ(n) is a sum of two squares has been studied by Banks, Luca, Saidak, and Shparlinski. Here we look at the corresponding three-squares question. We show that φ(n) is a sum of three squares precisely seven-eighths of the time. We also investigate the analogous problem with φ replaced by Carmichael's λ-function. We prove that the set of n for which λ(n) is a sum of three squares has lower density > 0 and upper density < 1.

  Hide this content.

• On some friends of the sociable numbers [PDF]
  Montash. Math. 162 (2010), no. 3, 321--327 [show abstract]

  Let s(n) denote the sum of the proper divisors of n. Set s₀(n) = n, and for k > 0, put s_k(n) := s(s_k-1(n)) if s_k-1(n) > 0. Thus, perfect numbers are those n with s(n)=n and amicable numbers are those n with s(n) ≠ n but s₂(n)=n. We prove that for each fixed k ≥ 1, the set of n which divide s_k(n) has density zero, and similarly for the set of n for which s_k(n) divides n. These results generalize the theorem of Erdős that for each fixed k, the set of n for which s_k(n)=n has density zero.

  Hide this content.

• Perfect numbers with identical digits [PDF]
  Integers 11A/Proceedings of the Integers Conference 2009 (2011), article 18, 11 pp. (electronic) [show abstract]

  Suppose g ≥ 2. A natural number N is called a repdigit in base g if it has the shape a (gⁿ-1)/(g-1) for some 1 ≤ a < g, i. e., if all of its digits in its base g expansion are equal. The number N is called perfect if σ(N) = 2N, where σ is the usual sum of divisors function. We show that in each base g, there are at most finitely many repdigit perfect numbers, and the set of all such numbers is effectively computable. Moreover, 6 is the only repdigit perfect number in base 10.

  Hide this content.

• The greatest common divisor of a number and its sum of divisors [PDF]
  Michigan Math. J. 60 (2011), 199--214 [show abstract]

  Let G(x, A) denote the number of natural numbers n ≤ x for which n and σ(n) have a common divisor exceeding A. We study the behavior of G(x, A) in a wide range of both variables. As a sample of our results, we show that if c is a fixed number in (0,1), then G(x, x^c) = x^1-c+o(1) as x goes to infinity.

  Hide this content.

• Quasi-amicable numbers are rare [PDF]
  J. Integer Sequences 14 (2011), article 11.5.2, 13 pp. (electronic) [show abstract]

  A quasi-amicable pair, such as {48, 75}, is a pair of distinct natural numbers each of which is the sum of the nontrivial divisors of the other. Here nontrivial excludes both 1 and the number itself. Such pairs have been studied (primarily empirically) by Garcia, Beck and Najar, Lal and Forbes, and Hagis and Lord. In this paper, we show that the set of n belonging to a quasi-amicable pair has asymptotic density zero.

  Hide this content.

• The exceptional set in the polynomial Goldbach problem [PDF]
  Int. J. Number Theory 7 (2011), 579--591 [show abstract]

  For each natural number N, let R(N) denote the number of representations of N as a sum of two primes. Hardy and Littlewood proposed a plausible asymptotic formula for R(2N) and showed, under the assumption of the Riemann Hypothesis for Dirichlet L-functions, that the formula holds "on average" in a certain sense. From this they deduced (under ERH) that all but O_ε(x^1/2+ε) of the even natural numbers in [1, x] can be written as a sum of two primes. We generalize their results to the setting of polynomials over a finite field. Owing to Weil's Riemann Hypothesis, our results are unconditional.

  Hide this content.

• An arithmetic function arising from Carmichael's conjecture (w/ F. Luca) [PDF]
  J. Théor. Nombres Bordeaux (to appear) [show abstract]

  Let φ denote Euler's totient function. A century-old conjecture of Carmichael asserts that for every n, the equation φ(n)=φ(m) has a solution m ≠ n. This suggests defining F(n) as the number of solutions m to the equation φ(n)=φ(m). (So Carmichael's conjecture asserts that F(n) ≥ 2 always.) Results on F are scattered throughout the literature. For example, Sierpiński conjectured, and Ford proved, that the range of F contains every natural number k ≥ 2. Also, the maximal order of F has been investigated by Erdős and Pomerance. In this paper we study the normal behavior of F. Let

  K(x) := (log x)^{(log log x)(log log log x)}.

  We prove that for every fixed ε > 0,

  K(n)^1/2-ε < F(n) < K(n)^3/2+ε

  for almost all natural numbers n. As an application, we show that φ(n)+1 is squarefree for almost all n. We conclude with some remarks concerning values of n for which F(n) is close to the conjectured maximum size.

  Hide this content.

• On common values of φ(n) and σ(m), I (w/ K. Ford) [PDF]
  Acta Math. Hungarica (to appear) [show abstract]

  We show, conditional on a uniform version of the prime k-tuples conjecture, that there are x/(log x)^1+o(1) numbers not exceeding x common to the ranges of φ and σ. Here φ is Euler's totient function and σ is the sum-of-divisors function.

  Hide this content.

• The Möbius transform and the infinitude of primes [PDF]
  Elem. Math. (to appear) [show abstract]

  Say that the pair of arithmetic functions (f, g) is a Möbius pair if, for all natural numbers n, f(n) is the sum of g(d), taken over all divisors d of n. In this case, one can express g in terms of f by the Möbius inversion formula familiar from elementary number theory. We give a simple proof that if (f, g) is a Möbius pair, then f and g cannot both be of finite support unless they both vanish identically. From this, we deduce another proof of Euclid's famous theorem that there are infinitely many prime numbers.

  Hide this content.

• On the parity of the number of multiplicative partitions and related problems [PDF]
  Proc. Amer. Math. Soc. (to appear) [show abstract]

  Let f(N) be the number of unordered factorizations of N, where a factorization is a way of writing N as a product of integers all larger than 1. For example, the factorizations of 30 are 2 × 3 × 5, 5 × 6, 3 × 10, 2 × 15, and 30, so that f(30)=5. The function f(N), as a multiplicative analogue of the (additive) partition function p(N), was first proposed by MacMahon, and its study was pursued by Oppenheim, Szekeres and Turán, and others. Recently, Zaharescu and Zaki showed that f(N) is even a positive proportion of the time and odd a positive proportion of the time. Here we show that for any arithmetic progression a mod m, the set of N for which f(N) ≡ a mod m possesses an asymptotic density. Moreover, the density is positive as long as there is at least one such N. For the case investigated by Zaharescu and Zaki, we show that f is odd more than 50% of the time (in fact, about 57%).

  Hide this content.

• Prime-perfect numbers (w/ C. Pomerance) [PDF]
  Integers, special issue in memory of J. L. Selfridge (to appear) [show abstract]

  We discuss a relative of the perfect numbers for which it is possible to prove that there are infinitely many examples. Call a natural number n prime-perfect if n and σ(n) share the same set of distinct prime divisors. For example, all even perfect numbers are prime-perfect. We demonstrate upper and lower bounds on the number of prime-perfects in [1,x]. We also discuss the analogous problem with σ replaced by Euler's φ function, and we answer some questions of Harborth and Cohen.

  Hide this content.

• On common values of φ(n) and σ(m), II (w/ K. Ford) [PDF], submitted.

• Two remarks on iterates of Euler's totient function [PDF], submitted.

• How many primes can divide the values of a polynomial? (w/ F. Luca) [PDF], submitted.

Book

• Not always buried deep: A second course in elementary number theory
  Published by the American Mathematical Society. Please consult the errata list here.

Waiting for their moment …

(In limbo.)

Ham. And thus the native hue of resolution is sicklied o'er with the pale cast of thought, and enterprises of great pith and moment with this regard their currents turn awry, and lose the name of action.

• On polynomial analogues of the Goldbach and twin prime conjectures (w/ A. Bender)

Talks

Ham. Speak the speech, I pray you, as I pronounced it to you, trippingly on the tongue: but if you mouth it, as many of our players do, I had as lief the town-crier spoke my lines. Nor do not saw the air too much with your hand, thus, but use all gently; for in the very torrent, tempest, and, as I may say, the whirlwind of passion, you must acquire and beget a temperance that may give it smoothness.

• Prime numbers and prime polynomials [PDF]
  Slides from my thesis defense.

• Primes, polynomials and patterns [PDF]
  Based on talks at Dartmouth's 2006 Exploring Math Program and the Ross Summer Mathematics Program 2007 reunion conference.

• Rational cubic reciprocity [PDF]

• The distribution of sociable numbers [PDF]
  See also: Sociable numbers, or How I messed with perfection and lived to write papers about it (2011 Joint Mathematics Meetings) [PDF]
  and: A perfect storm (U. Missouri, College of Charleston) [PDF]

• Two thousand years of summing divisors (Dartmouth colloquium) [PDF]

• Counting perfect numbers [PDF]

• N = ☐ + ☐ + ☐ [PDF], see also: 15-minute version for CNTA XI [PDF]

• The parity of the multiplicative partition function (2011 Illinois number theory meeting) [PDF]

Take me back to the page with you and the gorilla!