Papers
POLONIUS. What do you read, my lord?
HAMLET. Words, words, words.
Accepted Papers
-
An explicit approach to Hypothesis H for polynomials over finite fields
Anatomy of integers. Proceedings of a conference on the anatomy of integers, Montreal, March 13th-17th, 2006, J.-M. De Koninck, A. Granville, F. Luca, eds., CRM Proceedings and Lecture Notes, vol. 46, 2008, pp. 47--64
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 $\mathbf{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.
-
On a conjecture of Beard, O'Connell and West concerning perfect polynomials
Finite Fields and their Applications 14 (2008), no. 1, 242--249
Following Beard, O'Connell and West (1977) we call a polynomial over a finite field $\mathbf{F}_q$ perfect if it coincides with the sum of itself 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 $\mathbf{F}_2$ has a root in $\mathbf{F}_2$. 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\equiv 11\text{ or }17\bmod{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 $\mathbf{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 $\mathbf{F}_{11}$ with no linear factor.
-
Simultaneous prime specializations of polynomials over finite fields
Proc. London Math. Soc. 97 (2008), no. 3, 545--567
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 $\mathbf{F}_q[T]$ rather than $\mathbf{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.
-
A polynomial analogue of the twin prime conjecture
Proc. Amer. Math. Soc. 136 (2008), no. 11, 3775--3784
We consider the problem of counting the number of (not necessarily monic) `twin prime pairs' $P, P+M$ in $\mathbf{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^n\to\infty$ and then prove an explicit estimate confirming the conjecture in those cases where $q$ is large compared with $n^2$. 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.
-
Arithmetic properties of polynomial specializations over finite fields
Acta Arith. 136 (2009), no. 1, 57--79
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 $\mathbf{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.
-
On the distribution of sociable numbers
J. Number Theory 129 (2009), no. 8, 1990--2009
For a positive integer $n$, define $s(n)$ as the sum of the proper divisors of $n$. If $s(n) > 0$, define $s_2(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$ (as $x\to\infty$). 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$.
-
A remark on sociable numbers of odd order
J. Number Theory 130 (2010), no. 8, 1732--1736
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)), \ldots$ 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 \leq x$ of order $k$ is bounded by $x/(\log{x})^{1+o(1)}$ as $x\to\infty$. This improves on the previously best-known bound of $x/(\log\log{x})^{\frac{1}{2}+o(1)}$, due to Kobayashi, Pollack, and Pomerance.
-
Revisiting Gauss's analogue of the prime number theorem for polynomials over a finite field
Finite Fields and their Applications 16 (2010), no. 4, 290--299
In 1901, von Koch showed that the Riemann Hypothesis is equivalent to the assertion that $\pi(x)=\mathrm{Li}(x) + O(x^{1/2}\log{x})$. We describe an analogue of von Koch's result for polynomials over a finite prime field $\mathbf{F}_p$: For each natural number $n$, write $n$ in base $p$, say $n=a_0 + a_1 p + \cdots + a_k p^k$, and associate to $n$ the polynomial $a_0 + a_1 T + \cdots + a_k T^k$ in $\mathbf{F}_p[T]$. We let $\pi_p(X)$ denote the number of irreducible polynomials encoded by integers $n < X$, and prove a formula for $\pi_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 $\pi_p(X)$.
-
On polynomial rings with a Goldbach property
American Math. Monthly 118 (2011), no. 1, 71--77
David Hayes observed in 1965 that when $R=\mathbf{Z}$, every element of $R[T]$ of degree $n \geq 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.
-
On Dickson's theorem concerning odd perfect numbers
American Math. Monthly 118 (2011), no. 2, 161--164; errata in 118 (2011), no. 10, 953
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^{k^2}$.
-
Multiperfect numbers with identical digits
J. Number Theory 131 (2011), no. 2, 260--284
Let $g\geq 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 \frac{g^m-1}{g-1}$ for some $m \geq 1$ and some $D \in \{1, 2, \ldots, g-1\}$. We call $N$ perfect if $\sigma(N)=2N$, where $\sigma$ denotes the usual sum-of-divisors function. More generally, we call $N$ multiperfect if $\sigma(N)$ is a proper multiple of $N$. Pollack recently showed that for each fixed $g\geq 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.
-
Long gaps between deficient numbers
Acta Arith. 146 (2011), 33--42
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\to\infty$. We also prove that long runs of nondeficient numbers are scarce, in that the proportion of $n$ for which all of $n+1, n+2, \ldots, n+A$ are nondeficient decays triply exponentially in A.
-
Hypothesis H and an impossibility theorem of Ram Murty
Rend. Sem. Mat. Univ. Pol. Torino 68 (2010), 183--197
Dirichlet's 1837 theorem that every coprime arithmetic progression $a\bmod{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\bmod{m}$ satisfying $a^2\equiv 1\bmod{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^2\equiv 1\bmod{m}$.
-
On Hilbert's solution of Waring's problem
Cent. Eur. J. Math. 9 (2011), no. 2, 294--301
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 $k$th 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) \leq (2k+1)^{2000k^5}$.
-
Powerful amicable numbers
Colloq. Math. 122 (2011), 103--123
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 $\ell \geq 1$. A natural number $n$ is said to be $\ell$-full if $p^\ell \mid n$ for each prime $p$ dividing $n$. As shown by Erdős and Szekeres in 1935, the number of $\ell$-full integers $n \leq x$ is asymptotically $c_{\ell}x^{1/\ell}$ as $x\to\infty$. Here $c_{\ell}$ is a positive constant depending on $\ell$.
We show that for each fixed $\ell$, the set of amicable $\ell$-full numbers has relative density zero within the set of $\ell$-full numbers.
-
Values of the Euler and Carmichael functions which are sums of three squares
Integers 11 (2011), article A13, 16 pages (electronic)
Let $\varphi$ denote Euler's totient function. The frequency with which $\varphi(n)$ is a perfect square has been investigated by Banks, Friedlander, Pomerance, and Shparlinski, while the frequency with which $\varphi(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 $\varphi(n)$ is a sum of three squares precisely seven-eighths of the time. We also investigate the analogous problem with $\varphi$ replaced by Carmichael's $\lambda$-function. We prove that the set of $n$ for which $\lambda(n)$ is a sum of three squares has lower density $> 0$ and upper density $ < 1$.
-
On some friends of the sociable numbers
Monatsh. Math. 162 (2010), no. 3, 321--327
Let $s(n)$ denote the sum of the proper divisors of $n$. Let $s_0(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) \neq n$ but $s_2(n)=n$. We prove that for each fixed $k \geq 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 strengthen the theorem of Erdős that for each fixed $k$, the set of $n$ for which $s_k(n)=n$ has density zero.
-
Perfect numbers with identical digits
Integers 11A/Proceedings of the Integers Conference 2009 (2011), article 18, 11 pages (electronic)
Suppose $g \geq 2$. A natural number $N$ is called a repdigit in base $g$ if it has the shape $a \frac{g^n-1}{g-1}$ for some $1\leq a < g$, i.e., if all of its digits in its base $g$ expansion are equal. The number $N$ is called perfect if $\sigma(N)=2N$, where $\sigma$ 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$.
-
The greatest common divisor of a number and its sum of divisors
Michigan Math. J. 60 (2011), 199--214
Let $G(x,A)$ denote the number of natural numbers $n \leq x$ for which $\gcd(n,\sigma(n)) > 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 from the interval $(0,1)$, then $G(x,A)=x^{1-c+o(1)}$, as $x\to\infty$.
-
Quasi-amicable numbers are rare
J. Integer Sequences 14 (2011), article 11.5.2, 13 pages (electronic)
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.
-
The exceptional set in the polynomial Goldbach problem
Int. J. Number Theory 7 (2011), 579--591
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_{\epsilon}(x^{\frac{1}{2}+\epsilon})$ 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.
-
The Möbius transform and the infinitude of primes
Elem. Math. 66 (2011), 118--120
Say that the pair of arithmetic functions $(f, g)$ is a Möbius pair if $f(n)=\sum_{d \mid n}g(d)$ for all natural numbers $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.
-
Remarks on a paper of Ballot and Luca concerning prime divisors of $a^{f(n)}-1$
New York J. Math 17 (2011), 553--567
Fix an integer $a$ with $|a| > 1$, and fix a nonconstant, integer-valued polynomial $f(T) \in \mathbf{Q}[T]$ with positive leading term. Continuing investigations of Ballot and Luca, we study how many primes $p \leq x$ divide some expression of the form $a^{f(n)}-1$, where $n$ is a natural number. We improve the upper estimates found by Ballot and Luca, and on the assumption of the Generalized Riemann Hypothesis, establish an upper bound of the conjectured correct order of magnitude. We also formulate an asymptotic prediction for the number of such $p \leq x$, at least in the technically simpler case when $a > 0$. For example, we conjecture that the number of primes $p \leq x$ which divide $2^{n^2+1}-1$ for some $n$ is asymptotically $$\frac{7}{12\sqrt{2}}\left(\prod_{q\equiv 3\bmod{4}}\left(1-\frac{1}{q^2}\right)^{1/2}\left(1-\frac{1}{(q^2-1)(q-1)}\right)\right) \frac{x}{(\log{x})^{3/2}}.$$ Here the product is over all primes $q\equiv 3\bmod{4}$.
-
On common values of $\varphi(n)$ and $\sigma(m)$, I
Acta Math. Hungarica 133 (2011), 251--271
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 $\varphi$ and $\sigma$. Here $\varphi$ is Euler's totient function and $\sigma$ is the usual sum-of-divisors function.
-
Two remarks on iterates of Euler's totient function
Arch. Math. 97 (2011), 443--452
Let $\varphi_k$ denote the $k$th iterate of Euler's totient function. For each fixed $k$, we determine the asymptotic behavior of $\sum_{n \leq x}\varphi_k(n)$ and $\sum_{n \leq x}\frac{1}{\varphi_k(n)}$. We also show that for almost all primes $p$, there are at least roughly $\sqrt{\log{p}}$ distinct primes that divide some iterate $\varphi_k(n)$. The latter method has an implication for the classical problem of expressing roots of unity by radicals: For almost all numbers $n$, in order to reach an extension of $\mathbf{Q}$ containing a primitive $n$th root of unity by a sequence of prime radical extensions, the sequence must have length at least about $\sqrt{\log{n}}$.
-
An arithmetic function arising from Carmichael's conjecture
J. Théor. Nombres Bordeaux 23 (2011), 697--714
Let $\varphi$ denote Euler's totient function. A century-old conjecture of Carmichael asserts that for every $n$, the equation $\varphi(n)=\varphi(m)$ has a solution $m \neq n$. This suggests defining $F(n)$ as the number of solutions $m$ to the equation $\varphi(n)=\varphi(m)$. (So Carmichael's conjecture asserts that $F(n)\geq 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 \geq 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 each fixed $\epsilon > 0$, $$ K(n)^{\frac{1}{2}-\epsilon} < F(n) < K(n)^{\frac{3}{2}+\epsilon} $$ for almost all natural numbers $n$. As an application, we show that $\varphi(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. -
The average least quadratic nonresidue modulo $m$ and other variations on a theme of Erdős
J. Number Theory 132 (2012), 1185--1202
For each natural number $m\geq 3$, let $n_2(m)$ denote the least quadratic nonresidue modulo $m$. That is, $n_2(m)$ is the least integer $n \geq 1$ coprime to $m$ for which the congruence $x^2\equiv n \pmod{m}$ is insoluble. In 1961, Erdős showed that the mean value of $n_2(p)$, as $p$ runs over the odd primes, is given by $$\sum_{k=1}^{\infty}\frac{p_k}{2^k} \approx 3.675,$$ where $p_k$ denotes the $k$th prime in increasing order. Our first theorem gives the mean value of $n_2(m)$ without the restriction to prime values; it is $$\sum_{k=1}^{\infty}\frac{p_k-1}{p_1 p_2 \cdots p_{k-1}} \approx 2.920.$$ For each prime $p$, let $G(p)$ denote the least natural number $n$ so that the subgroup generated by $\{1, 2, \ldots, n\}$ is all of $(\mathbf{Z}/p\mathbf{Z})^{\times}$. For $p$ odd, $$n_2(p) \leq G(p) \leq g(p) < p,$$ where $g(p)$ is the least primitive root modulo $p$. Assuming the Generalized Riemann Hypothesis, we show that $G(p)$ possesses a finite mean value $\approx 3.975$. For $K$ a quadratic extension of $\mathbf{Q}$, let $n_K$ denote the smallest rational prime which is inert in $K$ and $r_K$ the least prime which is split in $K$. We show that if one orders quadratic fields by the absolute value of their discriminant, then $r_K$ and $n_K$ have the same mean value, which is $\approx 4.981$.
Erratum: Pieter Moree kindly pointed out that the method of evaluating singular series, developed in his cited Manuscripta Math. paper, differs substantially from that of Wrench. A more correct description of his results would be that they make effective earlier work of Dahlquist; see
G. Dahlquist, On the analytic continuation of Eulerian products. Ark. Mat. 1 (1952), 533–554.
-
On the parity of the number of multiplicative partitions and related problems
Proc. Amer. Math. Soc. 140 (2012), 3793--3803
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\times3\times5,\quad 5 \times 6,\quad 3 \times 10,\quad 2 \times 15,\quad\text{and}\quad 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\bmod{m}$, the set of $N$ for which $f(N)\equiv a\bmod{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\%$).
-
On perfect and near-perfect numbers
J. Number Theory 132 (2012), 3037--3046
We call $n$ a near-perfect number if $n$ is the sum of all of its proper divisors, except for one of them, which we term the redundant divisor. For example, the representation $$ 12=1 + 2 + 3 + 6 $$ shows that $12$ is near-perfect with redundant divisor $4$. Near-perfect numbers are thus a very special class of pseudoperfect numbers, as defined by Sierpiński. We discuss some rules for generating near-perfect numbers similar to Euclid's rule for constructing even perfect numbers, and we obtain an upper bound of $x^{5/6+o(1)}$ for the number of near-perfect numbers in $[1,x]$, as $x\to\infty$.
-
Prime-perfect numbers
Integers 12A/special issue in memory of J. L. Selfridge (2012), article A14, 19 pages (electronic)
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 $\sigma(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 $\sigma$ replaced by Euler's $\varphi$-function, and we answer some questions of Harborth and Cohen.
-
Finiteness theorems for perfect numbers and their kin
American Math. Monthly 119 (2012), 670--681; abridged errata in 120 (2013), 482--483
Since ancient times, a natural number has been called perfect if it equals the sum of its proper divisors; e.g., $6=1+2+3$ is a perfect number. In 1913, Dickson showed that for each fixed $k$, there are only finitely many odd perfect numbers with at most $k$ distinct prime factors. We show how this result, and many like it, follow from embedding the natural numbers in the supernatural numbers and imposing an appropriate topology on the latter; the notion of sequential compactness plays a starring role.
-
How many primes can divide the values of a polynomial?
Acta Arith. 156 (2012), 19--27
Let $F(T) \in \mathbf{Z}[T]$ be a nonconstant polynomial. We prove a result concerning the maximal order of $\Omega(F(n))$, where $\Omega(\cdot)$ denotes the total number of prime factors (counting multiplicity). In the case when $F$ has only simple roots, the result asserts that $$ \limsup_{n\to\infty}\frac{\Omega(F(n))}{\log{n}}=\frac{1}{\log{\ell}}, $$ where $\ell$ is the least prime for which $F$ has a zero in the $\ell$-adic integers $\mathbf{Z}_\ell$. This extends investigations of Erdős and Nicolas, who treated the case $F(T)=T(T+1)$.
-
On congruences of the form $\sigma(n)\equiv a\pmod{n}$
Int. J. Number Theory 9 (2012), 115--124
We study the distribution of solutions $n$ to the congruence $\sigma(n) \equiv a\pmod{n}$. After excluding obvious families of solutions, we show that the number of these $n \leq x$ is at most $x^{1/2+o(1)}$, as $x\to\infty$, uniformly for integers $a$ with $|a| \leq x^{1/4}$. As a concrete example, the number of composite solutions $n \leq x$ to the congruence $\sigma(n)\equiv 1\pmod{n}$ is at most $x^{1/2+o(1)}$. These results are analogues of theorems established for the Euler $\phi$-function by the third-named author (Carl Pomerance).
-
On common values of $\varphi(n)$ and $\sigma(m)$, II
Algebra Number Theory 6 (2012), no. 8, 1669--1696
For each positive-integer valued arithmetic function $f$, let $\mathcal{V}_{f}\subset \mathbf{N}$ denote the image of $f$, and put $\mathcal{V}_{f}(x) :=\mathcal{V}_f\cap [1,x]$ and $V_f(x) :=\#\mathcal{V}_f(x)$. Recently Ford, Luca, and Pomerance showed that $\mathcal{V}_{\phi}\cap\mathcal{V}_{\sigma}$ is infinite, where $\phi$ denotes Euler's totient function and $\sigma$ is the usual sum-of-divisors function. Work of Ford shows that $V_{\phi}(x) \asymp V_{\sigma}(x)$ as $x\to\infty$. Here we prove a result complementary to that of Ford et al., by showing that most $\phi$-values are not $\sigma$-values, and vice versa. More precisely, we prove that as $x\to\infty$, $$ \#\{n\leq x: n \in \mathcal{V}_{\phi}\cap \mathcal{V}_{\sigma}\}\leq \frac{V_{\phi}(x)+V_{\sigma}(x)}{(\log\log{x})^{1/2+o(1)}}. $$
-
The average least character nonresidue and further variations on a theme of Erdős
J. London Math. Soc. 87 (2013), 22--42
For each nonprincipal Dirichlet character $\chi$, let $n_{\chi}$ be the least $n$ with $\chi(n) \notin \{0,1\}$. For each prime $p$, let $\chi_p(\cdot)$ be the quadratic character modulo $p$. In 1961, Erdős showed that $n_{\chi_p}$ possesses a finite mean value as $p$ runs over the odd primes in increasing order. We show that as $q\to\infty$, the average of $n_{\chi}$ over all nonprincipal characters $\chi$ modulo $q$ is $\ell(q) +o(1)$, where $\ell(q)$ denotes the least prime not dividing $q$. Moreover, if one averages over all nonprincipal characters of moduli $\leq x$, the average approaches (as $x\to\infty$) the limiting value $$ \sum_{\ell}\frac{\ell^2}{\prod_{p \leq \ell}(p+1)}\approx 2.5350541804,$$ where the sum is over primes $\ell$ and the product is over primes $p \leq \ell$. One can also view Erdős's theorem as giving the average size of the least non-split prime in the quadratic field of conductor $p$, where again $p$ runs over odd primes. Similar results with the average taken over all quadratic fields were recently proved by the second author. In this paper, we prove a result of this type for cubic number fields: If one averages over all cubic fields $K$, ordered by discriminant, then the mean value of the least rational prime that does not split completely in $K$ is $$ \sum_{r}\frac{r(5/6+1/r+1/r^2)}{1+1/r+1/r^2}\prod_{p < r}\frac{1/6}{1+1/p+1/p^2}\approx 2.1211027269,$$ where the sum is over all primes $r$. Similar average values are obtained for the least rational prime with other specified factorizations in $K$, although some are conditional on the generalized Riemann hypothesis.
-
On the degrees of divisors of $T^n-1$
New York J. Math. 19 (2013), 91--116
Fix a field $F$. In this paper, we study the sets $\mathcal{D}_F(n) \subset [0,n]$ defined by $$ \mathcal{D}_F(n):= \{0 \leq m \leq n: T^n-1\text{ has a divisor of degree } m \text{ in } F[T]\}. $$ When $\mathcal{D}_F(n)$ consists of all integers $m$ with $0 \leq m \leq n$, so that $T^n-1$ has a divisor of every degree, we call $n$ an $F$-practical number. The terminology here is suggested by an analogy with the practical numbers of Srinivasan, which are numbers $n$ for which every integer $0 \leq m \leq \sigma(n)$ can be written as a sum of distinct divisors of $n$. Our first theorem states that, for any number field $F$ and any $x \geq 2$, $$ \#\{F \text{practical } n\leq x\} \asymp_{F} \frac{x}{\log{x}}; $$ this extends work of the second author, who obtained this estimate when $F=\mathbf{Q}$.
Suppose now that $x \geq 3$, and let $m$ be a natural number in $[3,x]$. We ask: For how many $n \leq x$ does $m$ belong to $\mathcal{D}_F(n)$? We prove upper bounds in this problem for both $F=\mathbf{Q}$ and $F=\mathbf{F}_p$ (with $p$ prime), the latter conditional on the Generalized Riemann Hypothesis. In both cases, we find that the number of such $n \leq x$ is $O_{F} (x/(\log{m})^{2/35})$, uniformly in $m$.
-
Irreducible polynomials with several prescribed coefficients
Finite Fields and their Applications 22 (2013), 70--78
We study the number of monic irreducible polynomials of degree $n$ over $\mathbf{F}_q$ having certain preassigned coefficients, where we assume that the constant term (if preassigned) is nonzero. Hansen and Mullen conjectured that for $n \geq 3$, one can always find an irreducible polynomial with any one coefficient preassigned (regardless of the ground field $\mathbf{F}_q$). Their conjecture was established in all but finitely many cases by Wan, and later resolved in full in work of Ham and Mullen. In this note, we present a new, explicit estimate for the number of irreducibles with several preassigned coefficients. One consequence is that for any $\epsilon >0$, and all $n \geq n_0(\epsilon)$, one can find a degree $n$ monic irreducible with any $\lfloor (1-\epsilon) \sqrt{n}\rfloor$ coefficients preassigned (uniformly in the choice of ground field $\mathbf{F}_q$). For the proof, we adapt work of Kátai and Harman on rational primes with preassigned digits.
-
Practical pretenders
Publ. Math. Debrecen 82 (2013), 651--667
Following Srinivasan, an integer $n\geq 1$ is called practical if every natural number in $[1,n]$ can be written as a sum of distinct divisors of $n$. This motivates us to define $f(n)$ as the largest integer with the property that all of $1, 2, 3, \ldots, f(n)$ can be written as a sum of distinct divisors of $n$. (Thus, $n$ is practical precisely when $f(n)\geq n$.) We think of $f(n)$ as measuring the ``practicality'' of $n$; large values of $f$ correspond to numbers $n$ which we term practical pretenders. Our first theorem describes the distribution of these impostors: Uniformly for $4 \leq y \leq x$, $$ \#\{n\leq x: f(n)\geq y\}\asymp \frac{x}{\log{y}}. $$ This generalizes Saias's result that the count of practical numbers in $[1,x]$ is $\asymp \frac{x}{\log{x}}$. Next, we investigate the maximal order of $f$ when restricted to non-practical inputs. Strengthening a theorem of Hausman and Shapiro, we show that every $n > 3$ for which $$ f(n) \geq \sqrt{e^{\gamma}n\log\log{n}}$$ is a practical number. Finally, we study the range of $f$. Call a number $m$ belonging to the range of $f$ an additive endpoint. We show that for each fixed $A >0$ and $\epsilon > 0$, the number of additive endpoints in $[1,x]$ is eventually smaller than $x/(\log{x})^A$ but larger than $x^{1-\epsilon}$.
-
Sets of monotonicity for Euler's totient function
Ramanujan J. 30 (2013), 379--398
We study subsets of $[1, x]$ on which the Euler $\varphi$-function is monotone (nondecreasing or nonincreasing). For example, we show that for any $\epsilon > 0$, every such subset has size smaller than $\epsilon x$, once $x > x_0(\epsilon)$. This confirms a conjecture of Pomerance.
-
On Mertens' theorem for Beurling primes
Canad. Math. Bull. 56 (2013), 829--843
Let $1 < p_1 \leq p_2 \leq p_3 \leq \cdots$ be an infinite sequence $\mathcal{P}$ of real numbers for which $p_i \to \infty$, and associate to this sequence the Beurling zeta function $$\zeta_{\mathcal{P}}(s):= \prod_{i=1}^{\infty}(1-p_i^{-s})^{-1}.$$ Suppose that for some constant $A>0$, we have $\zeta_{\mathcal{P}}(s) \sim A/(s-1)$, as $s\downarrow 1$. We prove that $\mathcal{P}$ satisfies an analogue of a classical theorem of Mertens: $$\prod_{p_i \leq x}(1-1/p_i)^{-1} \sim A e^{\gamma} \log{x},$$ as $x\to\infty$. Here $e = 2.71828\ldots$ is the base of the natural logarithm and $\gamma = 0.57721\ldots$ is the usual Euler--Mascheroni constant. This strengthens a recent theorem of Olofsson.
-
On the distribution of some integers related to perfect and amicable numbers
Colloq. Math. 30 (2013), 169--182
Let $s'(n) = \sum_{d \mid n,~1 < d < n} d$ be the sum of the nontrivial divisors of the natural number $n$, where nontrivial excludes both $1$ and $n$. For example, $s'(20)= 2 + 4 + 5 + 10 = 21$. A natural number $n$ is called quasiperfect if $s'(n)=n$, while $n$ and $m$ are said to form a quasiamicable pair if $s'(n)=m$ and $s'(m)=n$; in the latter case, both $n$ and $m$ are called quasiamicable numbers. In this paper, we prove two statistical theorems about these classes of numbers. First, we show that the count of quasiperfect $n \leq x$ is at most $x^{\frac14+o(1)}$, as $x\to\infty$. In fact, we show that for each fixed $a$, there are at most $x^{\frac14+o(1)}$ natural numbers $n \leq x$ with $\sigma(n)\equiv a\pmod{n}$ and $\sigma(n)$ odd. (Quasiperfect $n$ satisfy these conditions with $a=1$.) For fixed $\delta \neq 0$, define the arithmetic function $s_{\delta}(n) := \sigma(n)-n-\delta$. Thus, $s_{1} = s'$. Our second theorem says that the number of $n\leq x$ which are amicable with respect to $s_{\delta}$ is at most $x/(\log{x})^{1/2+o(1)}$.
-
The smallest inert prime in a cyclic number field of prime degree
Math. Res. Lett. 20 (2013), 163--179
Fix an odd prime $\ell$. For each cyclic extension $K/\mathbf{Q}$ of degree $\ell$, let $n_K$ denote the least rational prime which is inert in $K$, and let $r_K$ be the least rational prime which splits completely in $K$. We show that $n_K$ possesses a finite mean value, where the average is taken over all such $K$ ordered by conductor. As an example ($\ell=3$), the average least inert prime in a cyclic cubic field is approximately $2.870$.
We conjecture that $r_K$ also has a finite mean value, and we prove this assuming the Generalized Riemann Hypothesis. For the case $\ell=3$, we give an unconditional proof that the average of $r_K$ exists and is about $6.862$.
-
Paul Erdős and the rise of statistical thinking in elementary number theory
Erdős Centennial L. Lovász, I. Z. Ruzsa, and V. T. Sós, eds., János Bolyai Math. Soc. and Springer-Verlag, Hungary, 2013, pp. 515--523
This survey article discusses how Erdős's take on elementary number theory, with a focus on counting, changed the face of the subject, shedding new light on old problems and unearthing new mathematical worlds ripe for exploration.
-
Uncertainty principles connected with the Möbius inversion formula
Bull. Aust. Math. Soc. 88 (2013), 460--472
We say that two arithmetic functions $f$ and $g$ form a Möbius pair if $f(n) = \sum_{d \mid n} g(d)$ for all natural numbers $n$. In that case, $g$ can be expressed in terms of $f$ by the familiar Möbius inversion formula of elementary number theory. In a previous paper, the first-named author showed that if the members $f$ and $g$ of a Möbius pair are both finitely supported, then both functions vanish identically. Here we prove two significantly stronger versions of this uncertainty principle. A corollary is that in a nonzero Möbius pair, one cannot have both $\sum_{f(n) \neq 0}\frac{1}{n} <\infty$ and $\sum_{g(n) \neq 0}\frac{1}{n} <\infty$.
-
Equidistribution mod $q$ of abundant and deficient numbers
Uniform Distribution Theory 9 (2014), 99--114
The ancient Greeks called the natural number $m$ deficient, perfect, or abundant according to whether $\sigma(m) < 2m$, $\sigma(m)=2m$, or $\sigma(m)> 2m$. In 1933, Davenport showed that all three of these sets make up a well-defined proportion of the positive integers. More precisely, if we let $$ \mathcal{D}(u;x):=\left\{m \leq x: \frac{m}{\sigma(m)}\leq u\right\}, \quad\text{and put}\quad D(u;x):=\#\mathcal{D}(u;x), $$ then Davenport's theorem asserts that $\lim_{x\to\infty}\frac{1}{x}D(u;x)$ exists for every $u$. Moreover, $D(u)$ is a continuous function of $u$, with $D(0)=0$ and $D(1)=1$. In this note, we study the distribution of $\mathcal{D}(u;x)$ in arithmetic progressions. A simple to state consequence of our main result is the following: Fix $u \in (0,1]$. Then the elements of $\mathcal{D}(u;x)$ approach equidistribution modulo prime numbers $q$ whenever $q$, $x$, and $\frac{x}{q\log\log\log{x}}$ all tend to infinity.
-
A remark on prime divisors of partition functions
Int. J. Number Theory 10 (2014), 125--131
Schinzel showed that the set of primes that divide some value of the classical partition function is infinite. For a wide class of sets $\mathcal{A}$, we prove an analogous result for the function $p_{\mathcal{A}}(n)$ that counts partitions of $n$ into terms belonging to $\mathcal{A}$.
-
The error term in the count of abundant numbers
Mathematika 60 (2014), 43--65
A natural number $n$ is called abundant if the sum of the proper divisors of $n$ exceeds $n$. For example, $12$ is abundant, since $1 + 2 + 3 + 4 + 6=16$. In 1929, Bessel-Hagen asked whether or not the set of abundant numbers possesses an asymptotic density. In other words, if $A(x)$ denotes the count of abundant numbers belonging to the interval $[1,x]$, does $A(x)/x$ tend to a limit? Four years later, Davenport answered Bessel-Hagen's question in the affirmative. Calling this density $\Delta$, it is now known that $0.24761 < \Delta < 0.24766$, so that just under $1$ in $4$ numbers are abundant. We show that $A(x)-\Delta x < x/\exp((\log{x})^{1/3})$ for all large $x$. We also study the behavior of the corresponding error term for the count of so-called $\alpha$-abundant numbers.
-
The smallest prime that splits completely in an abelian number field
Proc. Amer. Math. Soc. 142 (2014), 1925--1934
Let $K/\mathbf{Q}$ be an abelian extension and let $D$ be the absolute value of the discriminant of $K$. We show that for each $\epsilon > 0$, the smallest rational prime that splits completely in $K$ is $O(D^{\frac14+\epsilon})$. Here the implied constant depends only on $\epsilon$ and the degree of $K$. This generalizes a theorem of Elliott, who treated the case when $K/\mathbf{Q}$ has prime conductor.
-
Square values of Euler's function
Bull. London Math. Soc. 46 (2014), 403--414
We show that almost all squares are missing from the range of Euler's totient function.
-
The primes that Euclid forgot
American Math. Monthly 121 (2014), 433--437
Let $q_1=2$. Supposing that we have defined $q_j$ for all $1 \leq j \leq k$, let $q_{k+1}$ be a prime factor of $1+\prod_{j=1}^{k} q_j$. As was shown by Euclid over two thousand years ago, $q_1, q_2, q_3, \ldots$ is then an infinite sequence of distinct primes. The sequence $\{q_i\}$ is not unique, since there is flexibility in the choice of the prime $q_{k+1}$ dividing $1 + \prod_{j=1}^{k}q_j$. Mullin suggested studying the two sequences formed by (1) always taking $q_{k+1}$ as small as possible, and (2) always taking $q_{k+1}$ as large as possible. For each of these sequences, he asked whether every prime eventually appears. Recently, Booker showed that the second sequence omits infinitely many primes. We give a completely elementary proof of Booker's result, suitable for presentation in a first course in number theory.
-
Variations on a theorem of Davenport concerning abundant numbers
Bull. Aust. Math. Soc. 89 (2014), 437--450
Let $\sigma(n) = \sum_{d \mid n}d$ be the usual sum-of-divisors function. In 1933, Davenport showed that $n/\sigma(n)$ possesses a continuous distribution function. In other words, the limit $D(u):= \lim_{x\to\infty} \frac{1}{x}\sum_{n \leq x,~n/\sigma(n) \leq u} 1$ exists for all $u \in [0,1]$ and varies continuously with $u$. We study the behavior of the sums $\sum_{n \leq x,~n/\sigma(n) \leq u} f(n)$ for certain complex-valued multiplicative functions $f$. Our results cover many of the more frequently encountered functions, including $\varphi(n)$, $\tau(n)$, and $\mu(n)$. They also apply to the representation function for sums of two squares, yielding the following analogue of Davenport's result: For all $u \in [0,1]$, the limit $$ \tilde{D}(u):= \lim_{R\to\infty} \frac{1}{\pi R}\#\{(x,y) \in \mathbf{Z}^2: 1 \leq x^2+y^2 \leq R \text{ and } \frac{x^2+y^2}{\sigma(x^2+y^2)} \leq u\} $$ exists, and $\tilde{D}(u)$ is both continuous and strictly increasing on $[0,1]$.
-
Prime splitting in abelian number fields and linear combinations of Dirichlet characters
Int. J. Number Theory 10 (2014), 885--903
Let $\mathbf{X}$ be a finite group of primitive Dirichlet characters. Let $\mathbf{\xi}=\sum_{\chi \in \mathbf{X}}a_{\chi}\chi$ be a nonzero element of the group ring $\mathbf{Z}[\mathbf{X}]$. We investigate the smallest prime $q$ that is coprime to the conductor of each $\chi \in \mathbf{X}$ and that satisfies $$ \sum_{\chi \in \mathbf{X}}a_{\chi}\chi(q) \neq 0. $$ Our main result is a nontrivial upper bound on $q$ valid for certain special forms $\mathbf{\xi}$. From this, we deduce upper bounds on the smallest unramified prime with a given splitting type in an abelian number field. For example:
- Let $p$ be a prime, and let $\chi$ be a Dirichlet character modulo $p$. Suppose that $\chi$ has order $n$ and that $d$ is a divisor of $n$ with $d > 1$. The least prime $q$ for which $\chi(q)$ is a primitive $d$th root of unity satisfies $$ q \ll_{n, \epsilon}p^{\lambda+\epsilon}, \quad\text{where}\quad \lambda=\frac{n}{8d}\cdot 2^{\omega(d)}. $$
- Let $K/\mathbf{Q}$ be an abelian number field of degree $n$ and conductor $f$. Let $g$ be a proper divisor of $n$. If there is any unramified rational prime $q$ that splits into $g$ distinct prime ideals in $\mathcal{O}_K$, then the least such $q$ satisfies $$ q \ll_{n, \epsilon}f^{\frac{n}{8}+ \epsilon}.$$
Our estimate also allows us to recover the upper bounds of Vinogradov--Linnik, Elliott, and the present author on the least split-completely prime in an abelian number field.
-
Averages of the number of points on elliptic curves
Algebra Number Theory 8 (2014), 813--836
If $E$ is an elliptic curve defined over $\mathbf{Q}$ and $p$ is a prime of good reduction for $E$, let $E(\mathbf{F}_p)$ denote the set of points on the reduced curve modulo $p$. Define an arithmetic function $M_E(N)$ by setting $M_E(N):=\#\{p\colon \#E(\mathbf{F}_p)=N\}$. Recently, David and the third author studied the average of $M_E(N)$ over certain "boxes" of elliptic curves $E$. Assuming a plausible conjecture about primes in short intervals, they showed the following: for odd $N$, the average of $M_E(N)$ over a box with sufficiently large sides is $\sim \frac{K^{\ast}(N)}{\log{N}}$ for an explicitly-given function $K^{\ast}(N)$. The function $K^{\ast}(N)$ is somewhat peculiar: defined as a product over the primes dividing $N$, it resembles a multiplicative function at first glance. But further inspection reveals that it is not, and so one cannot directly investigate its properties by the usual tools of multiplicative number theory. In this paper, we overcome these difficulties and prove a number of statistical results about $K^{\ast}(N)$. For example, we determine the mean value of $K^{\ast}(N)$ over odd $N$ and over prime $N$, and we show that $K^{\ast}(N)$ has a distribution function. We also explain how our results relate to existing theorems and conjectures on the multiplicative properties of $\#E(\mathbf{F}_p)$, such as Koblitz's conjecture.
-
Bounded gaps between primes with a given primitive root
Algebra Number Theory 8 (2014), 1769--1786
Fix an integer $g \neq -1$ that is not a perfect square. In 1927, Artin conjectured that there are infinitely many primes for which $g$ is a primitive root. Forty years later, Hooley showed that Artin's conjecture follows from the Generalized Riemann Hypothesis (GRH). We inject Hooley's analysis into the Maynard--Tao work on bounded gaps between primes. This leads to the following GRH-conditional result: Fix an integer $m \geq 2$. If $q_1 < q_2 < q_3 < \ldots$ is the sequence of primes possessing $g$ as a primitive root, then $\liminf_{n\to\infty}(q_{n+(m-1)}-q_n) \leq C_m$, where $C_m$ is a finite constant that depends on $m$ but not on $g$. We also show that the primes $q_n, q_{n+1}, \ldots, q_{n+m-1}$ in this result may be taken to be consecutive.
-
Some arithmetic properties of the sum of proper divisors and the sum of prime divisors
Illinois J. Math. 58 (2014), 125--147
For each positive integer $n$, let $s(n)$ denote the sum of the proper divisors of $n$. If $s(n)>0$, put $s_2(n)=s(s(n))$, and define the higher iterates $s_k(n)$ similarly. In 1976, Erdős proved the following theorem: For each $\delta > 0$ and each integer $K \geq 2$, we have $$ -\delta < \frac{s_{k+1}(n)}{s_k(n)}- \frac{s(n)}{n}$$ for all $1 \leq k < K$, except for a set of $n$ of asymptotic density zero. He also conjectured that $$ \frac{s_{k+1}(n)}{s_k(n)}- \frac{s(n)}{n} < \delta $$ for all $1\leq k < K$ and all $n$ outside of a set of density zero. This conjecture has proved rather recalcitrant and is known only when $K=2$, a 1990 result of Erdős, Granville, Pomerance, and Spiro. We re-prove their theorem in quantitative form, by what seems to be a simpler and more transparent argument. Similar techniques are used to investigate the arithmetic properties of the sum of the distinct prime divisors of $n$, which we denote by $\beta(n)$. We show that for a randomly chosen $n$, the integer $\beta(n)$ is squarefree with the same probability as $n$ itself. We also prove the same result with "squarefree" replaced by "abundant". Finally, we prove that for either of the functions $f(n)=s (n)$ or $f(n)=\beta(n)$, the number of $n\le x$ for which $f(n)$ is prime is $O(x/\log{x})$.
-
Euler and the partial sums of the prime harmonic series
Elem. Math. 70 (2015), 13--20
In a 1737 paper, Euler gave the first proof that the sum of the reciprocals of the prime numbers diverges. That paper can be considered as the founding document of analytic number theory, and its key innovation --- so-called Euler products --- are now ubiquitous in the field. In this note, we probe Euler's claim there that "the sum of the reciprocals of the prime numbers" is "as the logarithm" of the sum of the harmonic series. Euler's argument for this assertion falls far short of modern standards of rigor. Here we show how to arrange his ideas to prove the more precise claim that $$ \bigg|\sum_{\text{primes}p \leq x}\frac{1}{p}- \log\log{x}\bigg| < 6 $$ for all $x> e^4$.
-
Some normal numbers generated by arithmetic functions
Canad. Math. Bull. 58 (2015), 160--173
Let $g \geq 2$. A real number is said to be $g$-normal if its base $g$ expansion contains every finite sequence of digits with the expected limiting frequency. Let $\phi$ denote Euler's totient function, let $\sigma$ be the sum-of-divisors function, and let $\lambda$ be Carmichael's lambda-function. We show that if $f$ is any function formed by composing $\phi$, $\sigma$, or $\lambda$, then the number $$ 0. f(1) f(2) f(3) \ldots $$ obtained by concatenating the base $g$ digits of successive $f$-values is $g$-normal. We also prove the same result if the inputs $1, 2, 3, \ldots$ are replaced with the primes $2, 3, 5, \ldots$. The proof is an adaptation of a method introduced by Copeland and Erdős in 1946 to prove the $10$-normality of $0.235711131719\ldots$.
-
An easy generalization of Euler's theorem on the series of prime reciprocals
American Math. Monthly 122 (2015), 159--163
It is well-known that Euclid's argument can be adapted to prove the infinitude of primes of the form $4k-1$. We describe a simple proof that the sum of the reciprocals of all such primes diverges. More generally, if $q$ is a positive integer, and $H$ is a proper subgroup of the units group $(\mathbf{Z}/q\mathbf{Z})^{\times}$, we show that $$ \sum_{p\bmod{q} \notin H} \frac{1}{p}=\infty. $$
-
Bounded gaps between primes in number fields and function fields
Proc. Amer. Math. Soc. 143 (2015), 2841--2856
The Hardy--Littlewood prime $k$-tuples conjecture has long been thought to be completely unapproachable with current methods. While this sadly remains true, startling breakthroughs of Zhang, Maynard, and Tao have nevertheless made significant progress toward this problem. In this work, we extend the Maynard-Tao method to both number fields and the function field $\mathbf{F}_q(t)$.
-
The truth about torsion in the CM case
C. R. Math. Acad. Sci. Paris 353 (2015), 683--688
Let $T_{\mathrm{CM}}(d)$ be the maximum size of the torsion subgroup of an elliptic curve with complex multiplication defined over a degree $d$ number field. We show that there is an absolute, effective constant $C$ such that $T_{\mathrm{CM}}(d) \leq C d \log \log d$ for all $d \geq 3$.
-
Palindromic sums of proper divisors
Integers 15A/Proceedings of the Erdős Centennial Conference (2015), article A13 (electronic), 12 pages
Fix an integer $g \geq 2$. A natural number $n$ is called a palindrome in base $g$ if its base $g$ expansion reads the same forwards and backwards. Let $s(n)$ be the sum-of-proper-divisors function. We show that for almost all (that is, asymptotically 100% of) natural numbers $n$, $s(n)$ is not a palindrome in base $g$. We also show how to reach the same conclusion for several other commonly occurring arithmetic functions.
-
Harmonious pairs
Int. J. Number Theory 11 (2015), 1633--1651
Let $\sigma$ be the usual sum-of-divisors function. We say that $a$ and $b$ form a harmonious pair if $\frac{a}{\sigma(a)}+ \frac{b}{\sigma(b)}=1$; equivalently, the harmonic mean of $\frac{\sigma(a)}{a}$ and $\frac{\sigma(b)}{b}$ is $2$. For example, $4$ and $12$ form a harmonious pair, since $\frac{4}{\sigma(4)}=\frac{4}{7}$ and $\frac{12}{\sigma(12)}=\frac{3}{7}$. Every amicable pair is harmonious, but there are many others. We show that the count of numbers that belong to a harmonious pair having both members in $[1,x]$ is at most $x/\exp((\log{x})^{\frac{1}{12}+o(1)})$, as $x\to\infty$.
-
Arithmetic functions at consecutive shifted primes
Int. J. Number Theory 11 (2015), 1477--1498
For each of the functions $f \in \{\phi, \sigma, \omega, \tau\}$ and every natural number $K$, we show that there are infinitely many solutions to the inequalities $f(p_n-1) < f(p_{n+1}-1) < \cdots < f(p_{n+K}-1)$, and similarly for $f(p_n-1)> f(p_{n+1}-1) > \cdots > f(p_{n+K}-1)$. We also answer some questions of Sierpiński on the digit sums of consecutive primes. The arguments make essential use of Maynard and Tao's method for producing many primes in intervals of bounded length.
-
The length spectra of arithmetic hyperbolic 3-manifolds and their totally geodesic surfaces
New York J. Math 21 (2015), 955--972
In this paper we examine the relationship between the length spectrum and the geometric genus spectrum of an arithmetic hyperbolic $3$-orbifold $M$. In particular we analyze the extent to which the geometry of $M$ is determined by the closed geodesics coming from finite area totally geodesic surfaces. Using techniques from analytic number theory, we address the following problems: Is the commensurability class of an arithmetic hyperbolic $3$-orbifold determined by the lengths of closed geodesics lying on totally geodesic surfaces?, Do there exist arithmetic hyperbolic $3$-orbifolds whose "short" geodesics do not lie on any totally geodesic surfaces?, and Do there exist arithmetic hyperbolic $3$-orbifolds whose "short" geodesics come from distinct totally geodesic surfaces?
-
Besicovitch, bisection, and the normality of 0.(1)(4)(9)(16)(25)...
American Math. Monthly 122 (2015), 757--765
We revisit Besicovitch's 1935 paper in which he introduced several techniques that have become essential elements of modern combinatorial methods of normality proofs. Despite his paper's influence, the results he inspired are not strong enough to reprove his original result. We provide a new proof of the normality of the constant $0.(1)(4)(9)(16)(25)\cdots$ formed by concatenating the squares, updating Besicovitch's methods.
-
Remarks on fibers of the sum-of-divisors function
Analytic Number Theory: In Honor of Helmut Maier’s 60th Birthday M. Rassias and C. Pomerance, eds., Springer (2015), 305--320
Let $\sigma$ denote the usual sum-of-divisors function. We show that every positive real number can be approximated arbitrarily closely by a fraction $m/n$ with $\sigma(m)=\sigma(n)$. This answers in the affirmative a question of Erdős. We also show that for almost all of the elements $v$ of $\sigma(\mathbf{N})$, the members of the fiber $\sigma^{-1}(v)$ all share the same largest prime factor. We describe an application of the second result to the theory of L. E. Dickson's amicable tuples, which are a generalization of the ancient notion of an amicable pair.
-
On relatively prime amicable pairs
Mosc. J. Comb. Number Theory 5 (2015), 36--51
An amicable pair consists of two distinct numbers $N$ and $M$ each of which is the sum of the proper divisors of the other. For example, $220$ and $284$ form such a pair, as do $9773505$ and $11791935$. While over ten million such pairs are known, we know of no pair where $N$ and $M$ are relatively prime. Artjuhov and Borho have shown (independently) that if one fixes an upper bound on the number of distinct prime factors of $NM$, then there are only finitely many such coprime amicable pairs. We prove the following entirely explicit (but impractical) upper bound: If $N$ and $M$ form a coprime amicable pair with $\omega(NM)=K$, then $NM < (2K)^{2^{K^2}}$.
Some problems of Erdős on the sum-of-divisors function
Trans. Amer. Math. Soc. Ser. B. 3 (2016), 1--26
Let $\sigma(n)$ denote the sum of all of the positive divisors of $n$, and let $s(n)=\sigma(n)-n$ denote the sum of the proper divisors of $n$. The functions $\sigma(\cdot)$ and $s(\cdot)$ were favorite subjects of investigation by the late Paul Erdős. Here we revisit three themes from Erdős's work on these functions. First, we improve the upper and lower bounds for the counting function of numbers $n$ with $n$ deficient but $s(n)$ abundant, or vice versa. Second, we describe a heuristic argument suggesting the precise asymptotic density of $n$ not in the range of the function $s(\cdot)$; these are the so-called nonaliquot numbers. Finally, we prove new results on the distribution of friendly $k$-sets, where a friendly $k$-set is a collection of $k$ distinct integers all of which share the same value of $\frac{\sigma(n)}{n}$.
A Titchmarsh divisor problem for elliptic curves
Math. Proc. Cambridge Philos Soc. 160 (2016), 167--189
Let $E/\mathbb{Q}$ be an elliptic curve with complex multiplication. We study the average size of $\tau(\#E(\mathbb{F}_p))$ as $p$ varies over primes of good ordinary reduction. We work out in detail the case of $E\colon y^2=x^3-x$, where we prove that $$ \sum_{p \leq x,~p \equiv 1\pmod{4}}\tau(\#E(\mathbb{F}_p)) \sim \left(\frac{5\pi}{16}\prod_{p > 2}\frac{p^4-\chi(p)}{p^2(p^2-1)}\right)x, \quad\text{as } x\to\infty.$$ Here $\chi$ is the nontrivial Dirichlet character modulo $4$. The proof uses number field analogues of the Brun--Titchmarsh and Bombieri--Vinogradov theorems, along with a theorem of Wirsing on mean values of nonnegative multiplicative functions. Now suppose that $E/\mathbb{Q}$ is a non-CM elliptic curve. We conjecture that the sum of $\tau(\#E(\mathbb{F}_p))$, taken over $p \le x$ of good reduction, is $\sim c_E x$ for some $c_E >0$, and we give a heuristic argument suggesting the precise value of $c_E$. Assuming the Generalized Riemann Hypothesis for Dedekind zeta functions, we prove that this sum is $\asymp_{E}x$. The proof uses combinatorial ideas of Erdős.
The average of the first invariant factor for reductions of CM elliptic curves mod $p$
Int. Math. Res. Notices 2015 (2015), no. 21, 11333-11350
Let $E/\mathbf{Q}$ be a fixed elliptic curve. For each prime $p$ of good reduction, write $E(\mathbf{F}_p) \cong \mathbf{Z}/d_p \mathbf{Z}\oplus \mathbf{Z}/e_p \mathbf{Z}$, where $d_p \mid e_p$. Kowalski proposed investigating the average value of $d_p$ as $p$ runs over the rational primes. For CM curves, he showed that $x\log\log{x}/\log{x}\ll \sum_{p \le x}d_p \ll x\sqrt{\log{x}}$. It was shown recently by Felix and Murty that in fact $\sum_{p \le x}d_p$ exceeds any constant multiple of $x\log\log{x}/\log{x}$, once $x$ is sufficiently large. In the opposite direction, Kim has shown that the expression $x\sqrt{\log{x}}$ in the upper bound can be replaced by $x\log\log{x}$. In this paper, we obtain the correct order of magnitude for the sum: $\sum_{p \le x}d_p \asymp x$ for all large $x$.
A remark on divisor weighted sums
Ramanujan J. 40 (2016), 63--69
Let $\{a_n\}$ be a sequence of nonnegative real numbers. Under very mild hypotheses, we obtain upper bounds of the expected order of magnitude for sums of the form $\sum_{n \le x}a_n \tau_r(n)$, where $\tau_r(n)$ is the $r$-fold divisor function. This sharpens previous estimates of Friedlander and Iwaniec. The proof uses combinatorial ideas of Erdős and Wolke.
Bounded gaps between primes with a given primitive root, II
Forum Mathematicum 28 (2016), 675--687
Let $m$ be a natural number, and let $\mathcal{Q}$ be a set containing at least $\exp(C m)$ primes. We show that one can find infinitely many strings of $m$ consecutive primes each of which has some $q\in\mathcal{Q}$ as a primitive root, all lying in an interval of length $O_{\mathcal{Q}}(\exp(C'm))$. This is a bounded gaps variant of a theorem of Gupta and Ram Murty. We also prove a result on an elliptic analogue of Artin's conjecture. Let $E/\mathbf{Q}$ be an elliptic curve with an irrational $2$-torsion point. Assume GRH. Then for every $m$, there are infinitely many strings of $m$ consecutive primes $p$ for which $E(\mathbf{F}_p)$ is cyclic, all lying an interval of length $O_E(\exp(C'' m))$. If $E$ has CM, then the GRH assumption can be removed. Here $C$, $C'$, and $C''$ are absolute constants.
Subgroup avoidance for primes dividing the values of a polynomial
Rocky Mountain J. Math. 47 (2017), 2043--2050
For $f \in \mathbb{Q}[x]$, we say that a rational prime $p$ is a prime divisor of $f$ if $p$ divides the numerator of $f(n)$ for some integer $n$. Let $\mathcal{P}(f)$ denote the set of prime divisors of $f$. We present an elementary proof of the following theorem, which generalizes results of Mihály Bauer and Alfred Brauer: Fix a nonzero integer $g$. Suppose that $f(x) \in \mathbb{Q}[x]$ is a nonconstant polynomial having a root in $\mathbb{Q}_p$ for every prime $p$ dividing $g$, and having a root in $\mathbb{R}$ if $g < 0$. Let $m$ be a positive integer coprime to $g$ and let $H$ be a subgroup of $(\mathbb{Z}/m\mathbb{Z})^{\times}$ not containing $g\bmod{m}$. Then there are infinitely many primes $p \in \mathcal{P}(f)$ with $p\bmod{m}\notin H$.
Digitally delicate primes
J. Number Theory 168 (2016), 247--256
Tao has shown that in any fixed base, a positive proportion of prime numbers cannot have any digit changed and remain prime. In other words, most primes are "digitally delicate". We strengthen this result in a manner suggested by Tao: A positive proportion of primes become composite under any change of a single digit and any insertion a fixed number of arbitrary digits at the beginning or end.
Anatomy of torsion in the CM case
Math. Z. 285 (2017), 795--820
Let $T_{\mathrm{CM}}(d)$ denote the maximum size of a torsion subgroup of a CM elliptic curve over a degree $d$ number field. We initiate a systematic study of the asymptotic behavior of $T_{\mathrm{CM}}(d)$ as an arithmetic function. Whereas a recent result of the last two authors computes the upper order of $T_{\mathrm{CM}}(d)$, here we determine the lower order, the typical order and the average order of $T_{\mathrm{CM}}(d)$ as well as study the number of isomorphism classes of groups $G$ of order $T_{\mathrm{CM}}(d)$ which arise as the torsion subgroup of a CM elliptic curve over a degree $d$ number field. To establish these analytic results we need to extend some prior algebraic results. Especially, if $E_{/F}$ is a CM elliptic curve over a degree $d$ number field, we show that $d$ is divisible by a certain function of $\# E(F)[\mathrm{tors}]$, and we give a complete characterization of all degrees $d$ such that every torsion subgroup of a CM elliptic curve defined over a degree $d$ number field already occurs over $\mathbb{Q}$.
Torsion subgroups of CM elliptic curves over odd degree number fields
Int. Math. Res. Notices 2017 (2017), 4923--4961
Let $\mathcal{G}_{\mathrm {CM}}(d)$ denote the collection of groups (up to isomorphism) that appear as the torsion subgroup of a CM elliptic curve over a degree $d$ number field. We completely determine $\mathcal{G}_{\mathrm{CM}}(d)$ for odd integers $d$ and deduce a number of statistical theorems about the behavior of torsion subgroups of CM elliptic curves. Here are three examples: (1) For each odd $d$, the set of natural numbers $d'$ with $\mathcal{G}_{\mathrm{CM}}(d')=\mathcal{G}_{\mathrm{CM}}(d)$ possesses a well-defined, positive asymptotic density. (2) Let $T_{\mathrm{CM}}(d)=\max_{G \in \mathcal{G}_{\mathrm{CM}}(d)}\#G$; under the Generalized Riemann Hypothesis, $$ \left(\frac{12e^{\gamma}}{\pi}\right)^{2/3}\le \limsup_{d\to\infty,~d\text{odd}}\frac{T_{\mathrm{CM}}(d)}{(d\log\log{d})^{2/3}}\le \left(\frac{24e^{\gamma}}{\pi}\right)^{2/3}. $$ (3) For each $\epsilon > 0$, we have $\#\mathcal{G}_{\mathrm{CM}}(d) \ll_{\epsilon}d^{\epsilon}$ for all odd $d$; on the other hand, for each $A> 0$, we have $\#\mathcal{G}_{\mathrm{CM}}(d) > (\log{d})^A$ for infinitely many odd $d$.
Numbers divisible by a large shifted prime and large torsion subgroups of CM elliptic curves
Int. Math. Res. Notices 2017 (2017), 5525--5553
We sharpen a 1980 theorem of Erdős and Wagstaff on the distribution of positive integers having a large shifted prime divisor. Specifically, we obtain precise estimates for the quantity $N(x,y) := \#\{n \le x: \ell-1\mid n\text{ for some } \ell-1 > y, \ell \text{ prime}\},$ in essentially the full range of $x$ and $y$. We then present an application to a problem in arithmetic statistics. Let $T_{\mathrm{CM}}(d)$ denote the largest order of a torsion subgroup of a CM elliptic curve defined over a degree $d$ number field. Recently, Bourdon, Clark, and Pollack showed that the set of $d$ with $T_{\mathrm{CM}}(d) > y$ has upper density tending to $0$, as $y\to\infty$. We quantify the rate of decay to $0$, proving that the upper and lower densities of this set both have the form $(\log{y})^{-\beta+o(1)}$, where $\beta=1-\frac{1+\log\log{2}}{\log{2}}$ (the Erdős--Ford--Tenenbaum constant).
Bounds for the first several prime character nonresidues
Proc. Amer. Math. Soc. 145 (2017), 2815--2826
Let $\varepsilon > 0$. We prove that there are constants $m_0=m_0(\varepsilon)$ and $\kappa=\kappa(\varepsilon) > 0$ for which the following holds: For every integer $m > m_0$ and every nontrivial Dirichlet character modulo $m$, there are more than $m^{\kappa}$ primes $\ell \le m^{\frac{1}{4\sqrt{e}}+\varepsilon}$ with $\chi(\ell)\notin \{0,1\}$. The proof uses the fundamental lemma of the sieve, Norton's refinement of the Burgess bounds, and a result of Tenenbaum on the distribution of smooth numbers satisfying a coprimality condition. For quadratic characters, we demonstrate a somewhat weaker lower bound on the number of primes $\ell \le m^{\frac14+\epsilon}$ with $\chi(\ell)=1$.
A simple proof of a theorem of Hajdu--Jarden--Narkiewicz
Colloq. Math. 147 (2017), 217--220
Let $K$ be an algebraic number field, and let $G$ be a finitely generated subgroup of $K^{\times}$. We give a short proof that for every positive integer $n$, there is an element of $\mathcal{O}_K$ not expressible as a sum of $n$ elements of $G$.
The representation function for sums of three squares along arithmetic progressions
Proc. Japan Acad., Ser. A Math. Sci. 92 (2016), 96--99
For positive integers $n$, let $r(n) = \#\{(x,y,z) \in\mathbb{Z}^3: x^2+y^2+z^2=n\}.$ Let $g$ be a positive integer, and let $A\bmod{M}$ be any congruence class containing a squarefree integer. We show that there are infinitely many squarefree positive integers $n\equiv A\bmod{M}$ for which $g$ divides $r(n)$. This generalizes a result of Cho.
An elemental Erdős-Kac theorem for algebraic number fields
Proc. Amer. Math. Soc. 145 (2017), 971--987
Fix a number field $K$. For each nonzero $\alpha \in \mathbb{Z}_K$, let $\nu(\alpha)$ denote the number of distinct, nonassociate irreducible divisors of $\alpha$. We show that $\nu(\alpha)$ is normally distributed with mean proportional to $(\log\log |N(\alpha)|)^{D}$ and standard deviation proportional to $(\log\log{|N(\alpha)|})^{D-1/2}$. Here $D$, as well as the constants of proportionality, depend only on the class group of $K$. For example, for each fixed real $\lambda$, the proportion of $\alpha \in \mathbb{Z}[\sqrt{-5}]$ with $$\nu(\alpha) \le \frac{1}{8}(\log\log{N(\alpha)})^2 + \frac{\lambda}{2\sqrt{2}} (\log\log{N(\alpha)})^{3/2}$$ is given by $\frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\lambda} e^{-t^2/2}\, \mathrm{d}t$. As further evidence that "irreducibles play a game of chance", we show that the values $\nu(\alpha)$ are equidistributed modulo $m$ for every fixed $m$.
Clusters of primes with square-free translates
Rev. Mat. Iberoam. 33 (2017), 809--829
Let $\mathcal{R}$ be a finite set of integers satisfying appropriate local conditions. We show the existence of long clusters of primes $p$ in bounded length intervals with $p - b$ squarefree for all $b\in \mathcal{R}$. Moreover, we can enforce that the primes $p$ in our cluster satisfy any one of the following conditions: (1) $p$ lies in a short interval $[N,N + N^{7/12 + \epsilon}]$, (2) $p$ belongs to a given inhomogeneous Beatty sequence, (3) with $c\in (8/9, 1)$ fixed, $p^c$ lies in a prescribed interval mod 1 of length $p^{-1+c+\epsilon}$.
Extremal primes for elliptic curves with complex multiplication
J. Number Theory 172 (2017), 383--391
Fix an elliptic curve $E/\mathbb{Q}$. For each prime $p$ of good reduction, let $a_p = p+1-\#E(\mathbb{F}_p)$. A well-known theorem of Hasse asserts that $|a_p| \le 2\sqrt{p}$. We say that $p$ is a champion prime for $E$ if $a_p= -\lfloor 2\sqrt{p}\rfloor$, that is, $\#E(\mathbb{F}_p)$ is as large as allowed by the Hasse bound. Analogously, we call $p$ a trailing prime if $a_p = \lfloor 2\sqrt{p}\rfloor$. In this note, we study the frequency of champion and trailing primes for CM elliptic curves. Our main theorem is that for CM curves, both the champion primes and trailing primes have counting functions $\sim \frac{2}{3\pi} x^{3/4}/\log{x}$, as $x\to\infty$. This confirms (in corrected form) a recent conjecture of James--Tran--Trinh--Wertheimer--Zantout.
Addendum: Maknys's argument for the equidistribution result quoted as Proposition 2 is incomplete. In its place, one can substitute the following estimate, which is within the reach of current technology.
Proposition 2'. Let $K$ be an imaginary quadratic field. Fix $\mu, \nu \in \mathcal{O}_K$ with $\mu \ne 0$ and with $\nu\bmod{\mu}$ an invertible residue class. As $x\to\infty$, $$ \sum_{\substack{\varpi\text{ prime} \\ N\varpi \text{ prime} \\ x < N\varpi \le x+x/\log{x} \\ \varpi \equiv \nu \pmod{\mu} \\ \theta_1 < \arg\varpi <\theta_2}} 1 \sim \frac{w_K}{h_K \varphi(\mu)} \cdot \frac{\theta_2-\theta_1}{2\pi} \cdot \frac{x/\log{x}}{\log{x}}, $$ when $2\pi \ge \theta_2-\theta_1 > x^{-0.251}$. Here the estimate is uniform in the $\theta_i$.
Our proof requires only minor modifications (one should now define $\mathcal{X}(\varpi)= \{X \in \mathbb{R}: X< N\varpi \le X + X/\log{X}\}$). We thank Joshua Stucky for bringing this issue to our attention and for helpful correspondence.Two problems concerning irreducible elements in rings of integers of number fields
Bull. Aust. Math. Soc. 96 (2017), 44--58
Let $K$ be a number field with ring of integers $\mathbb{Z}_K$. We prove two asymptotic formulas connected with the distribution of irreducible elements in $\mathbb{Z}_K$. First, we estimate the maximum number of nonassociated irreducibles dividing a nonzero element of $\mathbb{Z}_K$ of norm not exceeding $x$ (in absolute value), as $x\to\infty$. Second, we count the number of irreducible elements of $\mathbb{Z}_K$ of norm not exceeding $x$ lying in a given arithmetic progression (again, as $x\to\infty$). When $K=\mathbb{Q}$, both results are classical; a new feature in the general case is the influence of combinatorial properties of the class group of $K$.
Eigenvalues of the Laplacian on domains with fractal boundary
Horizons of Fractal Geometry and Complex Dimensions. 2016 Summer School: Fractal Geometry and Complex Dimensions. In celebration of the 60th birthday of Michel Lapidus. R.G. Niemeyer, E.P.J. Pearse, J.A. Rock, T. Samuel, eds., AMS Contemporary Mathematics, vol. 731, 2019.
Consider the Laplacian operator on a bounded open domain in Euclidean space with Dirichlet boundary conditions. We show that for each number $D$ with $1< D < 2$, there are two bounded open domains in $\mathbb{R}^2$ of the same area, with their boundaries having Minkowski dimension $D$, and having the same content, yet the secondary terms for the eigenvalue counts are not the same. This was shown earlier by Lapidus and the second author, but a possible countable set of exceptional dimensions $D$ were excluded. Here we show that the earlier construction has no exceptions.
Systoles of arithmetic hyperbolic surfaces and 3-manifolds
Math. Res. Lett. 24 (2017), 1497--1522
Our main result is that for all sufficiently large $x_0>0$, the set of commensurability classes of arithmetic hyperbolic 2-- or 3--orbifolds with fixed invariant trace field $k$ and systole bounded below by $x_0$ has density one within the set of all commensurability classes of arithmetic hyperbolic 2-- or 3--orbifolds with invariant trace field $k$. The proof relies upon bounds for the absolute logarithmic Weil height of algebraic integers due to Silverman, Brindza and Hajdu, as well as precise estimates for the number of rational quaternion algebras not admitting embeddings of any quadratic field having small discriminant. When the trace field is $\mathbb{Q}$, using work of Granville and Soundararajan, we establish a stronger result that allows our constant lower bound $x_0$ to grow with the area. As an application, we establish a systolic bound for arithmetic hyperbolic surfaces that is related to prior work of Buser--Sarnak and Katz--Schaps--Vishne. Finally, we establish an analogous density result for commensurability classes of arithmetic hyperbolic 3--orbifolds with a small area totally geodesic $2$--orbifolds.
Refinements of Lagrange's four-square theorem
American Math. Monthly 125 (2018), 258--263
A well-known theorem of Lagrange asserts that every nonnegative integer $n$ can be written in the form $a^2+b^2+c^2+d^2$, where $a,b,c,d \in \mathbb{Z}$. We characterize the values assumed by $a+b+c+d$ as we range over all such representations of $n$.
The number of atoms in a primefree atomic domain
Comm. Algebra 45 (2017), 5431--5442
We study the number of atoms and maximal ideals in an atomic domain with finitely many atoms and no prime elements. We show in particular that for all $m,n \in \mathbb{Z}^+$ with $n \geq 3$ and $4 \leq m \leq \frac{n}{3}$ there is an atomic domain with precisely $n$ atoms, precisely $m$ maximal ideals and no prime elements. The proofs involve an interplay of commutative algebra, algebraic number theory and additive number theory.
The truth about torsion in the CM case, II
Quart. J. Math. 68 (2017), 1313--1333
Let $T_{{\mathrm{CM}}}(d)$ be the largest size of the torsion subgroup of an elliptic curve with complex multiplication (CM) defined over a degree $d$ number field. Work of Breuer and Clark--Pollack showed $\limsup_{d \to \infty} \frac{T_{{\mathrm{CM}}}(d)}{d \log \log d} \in (0,\infty)$. Here we show that the above limit supremum is precisely $\frac{e^{\gamma} \pi}{\sqrt{3}}$. We also study -- in part, out of necessity -- the upper order of the size of the torsion subgroup of various restricted classes of CM elliptic curves over number fields.
Counting perfect polynomials
Finite Fields and their Applications 47 (2017), 242--255
Let $A \in \mathbb{F}_2[T]$. We say $A$ is perfect if $A$ coincides with the sum of all of its divisors in $\mathbb{F}_2[T]$. We prove that the number of perfect polynomials $A$ with $|A| \le x$ is $O_{\epsilon}(x^{1/12+\epsilon})$ for all $\epsilon>0$, where $|A| = 2^{\deg{A}}$. We also prove that every perfect polynomial $A$ with $1 < |A| \le 1.6\times 10^{60}$ is divisible by $T$ or $T+1$; that is, there are no small ``odd'' perfect polynomials.
Thue's lemma in $\mathbb{Z}[i]$ and Lagrange's four-square theorem
Elem. Math. 73 (2018), 60--65
Without question, two of the most significant results of pre-19th century number theory are (a) Fermat's theorem that every prime $p\equiv 1\pmod{4}$ is a sum of two squares, and (b) Lagrange's theorem that every positive integer is a sum of four squares. Today, several proofs are known for both of these theorems. Perhaps the simplest proof of Fermat's theorem uses a beautiful combinatorial lemma of Axel Thue: For any $a$ and $m$, the congruence $ax\equiv y\pmod{m}$ has a ``small'' solution $x,y$ other than the trivial solution $(0,0)$. Here ``small'' means that $|x|, |y| \le \sqrt{m}$. In 2010, Jameson gave a short, simple proof of Lagrange's theorem based on an extension of Thue's lemma to the Gaussian integers. Here we show how using a bit more of the arithmetic of $\mathbb{Z}[i]$ allows one to give a conceptually simpler proof based on these same ideas.
Clustering of linear combinations of multiplicative functions
J. Number Theory 180 (2017), 660--672
A real-valued arithmetic function $F$ is said to cluster about the point $u \in \mathbb{R}$ if the upper density of $n$ with $u-\delta < F(n) < u+\delta$ is bounded away from $0$, uniformly for all $\delta > 0$. We establish a simple-to-check sufficient condition for a linear combination of multiplicative functions to be nonclustering, meaning not clustering anywhere. This provides a means of generating new families of arithmetic functions possessing continuous distribution functions. As a specific application, we resolve a problem posed recently by Luca and Pomerance.
Bounded gaps between primes and the length spectra of arithmetic hyperbolic 3-orbifolds
C. R. Math. Acad. Sci. Paris 355 (2017), 1121--1126
In 1992, Reid asked whether hyperbolic $3$--manifolds with the same geodesic length spectra are necessarily commensurable. While this is known to be true for arithmetic hyperbolic $3$--manifolds, the non-arithmetic case is still open. Building towards a negative answer to this question, Futer and Millichap recently constructed infinitely many pairs of non-commensurable, non-arithmetic hyperbolic $3$--manifolds which have the same volume and whose length spectra begin with the same first $m$ geodesic lengths. In the present paper, we show that this phenomenon is surprisingly common in the arithmetic setting. In particular, given any arithmetic hyperbolic $3$--orbifold derived from a quaternion algebra, any finite subset $S$ of its geodesic length spectrum, and any $k \geq 2$, we produce infinitely many $k$--tuples of arithmetic hyperbolic $3$--orbifolds which are pairwise non-commensurable, have geodesic length spectra containing $S$, and have volumes lying in an interval of (universally) bounded length. The main technical ingredient in our proof is a bounded gaps result for prime ideals in number fields lying in Chebotarev sets which extends recent work of Thorner.
Divisor-sum fibers
Mathematika 64 (2018), 330--342
Let $s(\cdot)$ denote the sum-of-proper-divisors function, that is, $s(n) = \sum_{d\mid n,~ d < n} d$. Erdős--Granville--Pomerance--Spiro conjectured that for any set $\mathcal{A}$ of asymptotic density zero, the preimage set $s^{-1}(\mathcal{A})$ also has density zero. We prove a weak form of this conjecture: If $\epsilon(x)$ is any function tending to $0$ as $x\to\infty$, and $\mathcal{A}$ is a set of integers of cardinality at most $x^{\frac12+\epsilon(x)}$, then the number of integers $n\le x$ with $s(n) \in \mathcal{A}$ is $o(x)$, as $x\to\infty$. In particular, the EGPS conjecture holds for infinite sets with counting function $O(x^{\frac12 + \epsilon(x)})$. We also disprove a hypothesis from the same paper of EGPS by showing that for any positive numbers $\alpha$ and $\epsilon$, there are integers $n$ with arbitrarily many $s$-preimages lying between $\alpha(1-\epsilon)n$ and $\alpha(1+\epsilon)n$. Finally, we make some remarks on solutions $n$ to congruences of the form $\sigma(n) \equiv a\pmod{n}$, proposing a modification of a conjecture appearing in recent work of the first two authors. We also improve a previous upper bound for the number of solutions $n \leq x$, making it uniform in $a$.
Pursuing polynomial bounds on torsion
Israel J. Math. 227 (2018), 889--909
We show that for all $\epsilon > 0$, there is a constant $C(\epsilon) > 0$ such that for all elliptic curves $E$ defined over a number field $F$ with $j(E) \in \mathbb{Q}$ we have $$\# E(F)[\mathrm{tors}] \leq C(\epsilon) [F:\mathbb{Q}]^{5/2 + \epsilon}.$$ We pursue further bounds on the size of the torsion subgroup of an elliptic curve over a number field $E_{/F}$ that are polynomial in $[F:\mathbb{Q}]$ under restrictions on $j(E)$. We give an unconditional result for $j(E)$ lying in a fixed quadratic field that is not imaginary of class number one as well as two further results, one conditional on GRH and one conditional on the strong boundedness of isogenies of prime degree for non-CM elliptic curves.
The least prime quadratic nonresidue in a prescribed residue class mod $4$
J. Number Theory 187 (2018), 403--414
For all primes $p \ge 5$, there is a prime quadratic nonresidue $q < p$ with $q\equiv 3\pmod{4}$. For all primes $p\ge 13$, there is a prime quadratic nonresidue $q < p$ with $q\equiv 1\pmod{4}$.
Dirichlet's proof of the three-square theorem: an algorithmic perspective
Math. Comp. 88 (2019), 1007--1019
The Gauss--Legendre three-square theorem asserts that the positive integers $n$ expressible as a sum of three integer squares are precisely those not of the form $4^k(8m+7)$ for any nonnegative integers $k,m$. In 1850, Dirichlet gave a beautifully simple proof of this result using only basic facts about ternary quadratic forms. We explain how to turn Dirichlet's proof into an algorithm; if one assumes the Extended Riemann Hypothesis (ERH), there is a random algorithm for expressing $n=x^2+y^2+z^2$ where the expected number of bit operations is $O((\lg n)^2 (\lg \lg n)^{-1} \cdot M(\lg n))$. Here $M(r)$ stands in for the bit complexity of multiplying two $r$-bit integers. A random algorithm for this problem of similar complexity was proposed by Rabin and Shallit in 1986; however, their analysis depended on both the ERH and on certain conjectures of Hardy--Littlewood type.
A note on Golomb topologies
Quaestiones Mathematicae 42 (2019), 73--86
In 1959 Golomb defined a connected topology on $\mathbb{Z}$. An analogous Golomb topology on an arbitrary integral domain was defined first by Knopfmacher-Porubský and then again in a recent work of Clark. Here we study properties of Golomb topologies.
Typically bounding torsion
J. Number Theory 192 (2018), 150--167
We formulate the notion of typical boundedness of torsion on a family of abelian varieties defined over number fields. This means that the torsion subgroups of elements in the family can be made uniformly bounded by removing from the family all abelian varieties defined over number fields of degree lying in a set of arbitrarily small density. We show that for each fixed $g$, torsion is typically bounded on the family of all $g$-dimensional CM abelian varieties. We show that torsion is not typically bounded on the family of all elliptic curves, and we establish results -- some unconditional and some conditional -- on typical boundedness of torsion of elliptic curves for which the degree of the $j$-invariant is fixed.
Finding the four squares in Lagrange's theorem
Integers 18A (2018), article A15, 16 pages (electronic)
In 1986, Rabin and Shallit presented three randomized algorithms to compute, given a positive integer $n$, integers $X,Y,Z,W$ with $X^2+Y^2+Z^2+W^2=n$. The fastest of the three has expected runtime $O((\log n)^2)$, but this runtime analysis assumes the truth of the Extended Riemann Hypothesis. (Here we measure runtime not by bit operations, but by the number of ``basic operations'' one must carry out on numbers of size at most $n^{O(1)}$.) The other two algorithms admit slightly worse runtime estimates but are unconditional, in the sense that no unproved hypotheses are used in the proof of correctness or the running-time analysis. In this paper we explain how to modify their algorithms to do slightly better. We give two algorithms for this problem with expected runtime $O((\log n)^2 (\log \log n)^{-1})$; the first is easily described but depends on ERH, while the latter is unconditional but slightly involved.
A remark on the number field analogue of Waring's constant $g(k)$
Math. Nachr. 291 (2018), 1893--1898
Let $K$ be a number field, and let $k$ be an integer with $k \ge 2$. Let $\mathcal{O}^{\ge 0}$ be the collection of totally nonnegative integers in $K$ (i.e., the totally positive integers together with zero). We let $g(k,K)$ denote the smallest positive integer with the following property: Every element of $\mathcal{O}^{\ge 0}$ that is a sum of $k$th powers of elements of $\mathcal{O}^{\ge 0}$ is the sum of $g$ such $k$th powers. Work of Siegel in the 1940s shows that $g(k,K)$ is well-defined for all $k$ and $K$. In this note, we prove that $g(k,K)$ cannot be bounded by a function of $k$ alone: For each $k\ge 2$, $$ \sup_{K} g(k,K) = \infty. $$
Counting and effective rigidity in algebra and geometry
Invent. Math. 213 (2018), 697--758
The purpose of this article is to produce effective versions of some rigidity results in algebra and geometry. On the geometric side, we focus on the spectrum of primitive geodesic lengths (resp., complex lengths) for arithmetic hyperbolic 2–manifolds (resp., 3–manifolds). By work of Reid, this spectrum determines the commensurability class of the 2–manifold (resp., 3–manifold). We establish effective versions of these rigidity results by ensuring that, for two incommensurable arithmetic manifolds of bounded volume, the length sets (resp., the complex length sets) must disagree for a length that can be explicitly bounded as a function of volume. We also prove an effective version of a similar rigidity result established by the second author with Reid on a surface analog of the length spectrum for hyperbolic 3–manifolds. These effective results have corresponding algebraic analogs involving maximal subfields and quaternion subalgebras of quaternion algebras. To prove these effective rigidity results, we establish results on the asymptotic behavior of certain algebraic and geometric counting functions which are of independent interest.
Waring's problem for integral quaternions
Indag. Math. 29 (2018), 1259--1269
A (Lipschitz) integral quaternion is a Hamiltonian quaternion of the form $a+bi+cj+dk$ with all of $a,b,c,d \in \mathbb{Z}$. In 1946, Niven showed that the integral quaternions expressible as a sum of squares of integral quaternions are precisely those for which $2\mid b, c, d$; moreover, all of these are expressible as sums of three squares. Now let $m$ be an integer with $m > 2$, and suppose $2^r \parallel m$. We show that if $r=0$ (i.e., $m$ is odd), then all integral quaternions are sums of $m$th powers, while if $r>0$, then the integral quaternions that are sums of $m$th powers are precisely those for which $2^r\mid b,c,d$ and $2^{r+1}\mid b+c+d$. Moreover, all of these are expressible as a sum of $g(m)$ $m$th powers, where $g(m)$ is a positive integer depending only on $m$.
Small prime $k$th power residues for $k=2, 3, 4$: a reciprocity laws approach
Proc. Amer. Math. Soc. 147 (2018), 987--994
Nagell proved that for each prime $p\equiv 1\pmod{3}$, $p>7$, there is a prime $q < 2p^{1/2}$ that is a cubic residue modulo $p$. Here we show that for each fixed $\epsilon > 0$, and each prime $p\equiv 1\pmod{3}$ with $p>p_0(\epsilon)$, the number of prime cubic residues $q < p^{\epsilon/30}$ exceeds $p^{\epsilon/30}$. Our argument, like Nagell's, is rooted in the law of cubic reciprocity; somewhat surprisingly, character sum estimates play no role. We use the same method to establish related results about prime quadratic and biquadratic residues. For example, for all large primes $p$, there are more than $p^{1/9}$ prime quadratic residues $q < p$.
A note on the least prime that splits completely in a nonabelian Galois number field
Math. Z. 292 (2019), 183--192
We prove a nontrivial estimate for the size of the least rational prime that splits completely in the ring of integers of certain families of nonabelian Galois number fields. Our result complements results of Linnik and Vinogradov and of Pollack who studied this problem in the quadratic and abelian number field settings, respectively.
How often is Euler's totient a perfect power?
J. Number Theory 197 (2019), 1--12
Fix an integer $k\ge 2$. We investigate the number of $n \le x$ for which $\phi(n)$ is a perfect $k$th power. If we assume plausible conjectures on the distribution of smooth shifted primes, then the count of such $n$ is at least $x/L(x)^{1+o(1)}$, as $x\to\infty$, where $L(x) = \exp(\log x\cdot \log \log \log x/\log \log x)$. This lower bound is implicit in work of Banks--Friedlander--Pomerance--Shparlinski. We prove --- unconditionally --- that $x/L(x)^{1+o(1)}$ serves as an upper bound. In fact, we establish this same bound for the count of $n\le x$ for which $\phi(n)$ is squarefull. The proof builds on methods recently introduced by the author to study "popular subsets" for Euler's function.
Popular subsets for Euler's $\varphi$-function
Math. Ann. 374 (2019), 253--271
Let $\varphi(n) = \#(\mathbb{Z}/n\mathbb{Z})^{\times}$ (Euler's totient function). Let $\epsilon > 0$, and let $\alpha \in (0,1)$. We prove that for all $x > x_0(\epsilon,\alpha)$ and every subset $\mathcal{S}$ of $[1,x]$ with $\#\mathcal{S} \le x^{1-\alpha}$, the number of $n\le x$ with $\varphi(n)\in \mathcal{S}$ is at most $x/L(x)^{\alpha-\epsilon}$, where $$ L(x) = \exp(\log x\cdot \log_3{x}/\log_2 x). $$ Under plausible conjectures on the distribution of smooth shifted primes, this upper bound is best possible, in the sense that the number $\alpha$ appearing in the exponent of $L(x)$ cannot be replaced by anything larger.
Nonnegative multiplicative functions on sifted sets, and the square roots of -1 modulo shifted primes
Glasgow Math. J. 62 (2020), 187--199
An oft-cited result of Peter Shiu bounds the mean value of a nonnegative multiplicative function over a coprime arithmetic progression. We prove a variant where the arithmetic progression is replaced by a sifted set. As an application, we show that the normalized square roots of $-1\pmod{m}$ are equidistributed (mod 1) as $m$ runs through the shifted primes $q-1$.
The smallest root of a polynomial congruence
Math. Res. Lett. 27 (2020), 43--66
Fix $f(t) \in \mathbb{Z}[t]$ having degree at least $2$ and no multiple roots. We prove that as $k$ ranges over those integers for which the congruence $f(t)\equiv 0\pmod{k}$ is solvable, the least nonnegative solution is almost always smaller than $k/(\log{k})^{c_f}$. Here $c_f$ is a positive constant depending on $f$. The proof uses a method of Hooley originally devised to show that the roots of $f$ are equidistributed modulo $k$ as $k$ varies.
Twists of hyperelliptic curves by integers in progressions modulo $p$
Acta Arith. 192 (2020), 63--71
Let $f(x)$ be a nonconstant polynomial with integer coefficients and nonzero discriminant. We study the distribution modulo primes of the set of squarefree integers $d$ such that the curve $dy^2 =f(x)$ has a nontrivial rational or integral point.
Reciprocity by resultant in $k[t]$
L’Enseignement Mathématique 65 (2019), 101--116
Let $k$ be a perfect field with procyclic absolute Galois group and containing a primitive $n$-th root of unity. We define a degree $n$ power residue symbol $(\frac{a}{b})_n$ in the ring $k[t]$, show that it is equal to "the character of the resultant $\mathrm{Res}(b,a)$" and deduce a reciprocity law. We are motivated by commonalities between the classical case $k = \mathbb{F}_q$ and the novel but very simple case $k = \mathbb{R}$.
Multiplicative partitions of numbers with a large squarefree divisor
Ramanujan J. 53 (2020), 595--605
For each positive integer $n$, let $f(n)$ denote the number of multiplicative partitions of $n$, meaning the number of ways of writing $n$ as a product of integers larger than $1$, where the order of the factors is not taken into account. It was shown by Oppenheim in 1926 that, as $x\to\infty$, $$ \max_{n \le x,~n\text{ squarefree}} f(n) = x/L(x)^{2+o(1)},$$ where $L(x) = \exp(\log x\cdot \frac{\log\log\log{x}}{\log\log x})$. Without the restriction to squarefree $n$, the maximum is the significantly larger quantity $x/L(x)^{1+o(1)}$; this was proved by Canfield, Erdős, and Pomerance in 1983. We prove the following theorem that interpolates between these two results: For each fixed $\alpha \in [0,1]$, $$ \max_{n \le x,~\mathrm{rad}(n) \ge n^{\alpha}} f(n) = x/L(x)^{1+\alpha+o(1)}. $$ We deduce, on the abc-conjecture, a nontrivial upper bound on how often values of certain polynomials appear in the range of Euler's $\phi$-function.
On ordered factorizations into distinct parts
Proc. Amer. Math. Soc. 148 (2020), 1447--1453
Let $g(n)$ denote the number of ordered factorizations of $n$ into integers larger than $1$. In the 1930s, Kalmár and Hille investigated the average and maximal order of $g(n)$. In this note we examine these questions for the function $G(n)$ counting ordered factorizations into distinct parts. Concerning the average of $G(n)$, we show that $$ \sum_{n \le x} G(n) = x \cdot L(x)^{1+o(1)}, $$ where $$ L(x) = \exp\left(\log{x} \cdot \frac{\log \log\log {x}}{\log\log{x}}\right). $$ It follows that immediately that $G(n) \le n \cdot L(n)^{1+o(1)}$, as $n\to\infty$. We show that equality holds here on a sequence of $n$ tending to infinity, so that $n \cdot L(n)^{1+o(1)}$ represents the maximal order of $G(n)$.
Symmetric primes revisited
Integers 19 (2019), article A54, 7 pages
A pair of odd primes is said to be symmetric if each prime is congruent to one modulo their difference. A theorem from 1996 by Fletcher, Lindgren, and the third author provides an upper bound on the number of primes up to $x$ that belong to a symmetric pair. In the present paper, that theorem is improved to what is likely to be the best possible result. We also establish that there exist infinitely many symmetric pairs of primes. In fact, we show that for every integer $m\ge 2$ there is a string of $m$ consecutive primes, any two of which form a symmetric pair.
On sums of consecutive triangular numbers
Integers 20A (2020), article A15, 10 pages (electronic)
By a
triangular number , we mean one of the numbers $\Delta_n:=\frac{1}{2}n(n+1)$, for some $n = 1,2,3, \ldots$. In a recent Math Horizons note, Matthew McMullen suggested studying triangular sums of consecutive triangular numbers. In other words, one seeks solutions to equations of the form $$ \Delta_{n} + \cdots + \Delta_{n+(k-1)} = \Delta_{m}. $$ McMullen classified the solutions when $2\le k\le 5$; there are no solutions when $k=4$, while in the other cases, there are infinitely many solutions. He asked if there is a value of $k>4$ for which there are no solutions. Here we show that there are solutions for every square value of $k$ larger than $4$, but that for almost all values of $k$ (asymptotically 100%), there are no solutions.A generalization of the Hardy-Ramanujan inequality and applications
J. Number Theory 210 (2020), 171--182
Let $\omega(n)$ denote the number of distinct prime factors of the positive integer $n$. In 1917, Hardy and Ramanujan showed that for all real numbers $x\ge 2$ and all positive integers $k$, $$ \sum_{n \le x,~\omega(n)=k} 1 \le C \frac{x}{\log{x}} \frac{(\log\log{x}+D)^{k-1}}{(k-1)!}, $$ where $C$ and $D$ are absolute constants. We derive an analogous result when the summand $1$ is replaced by $f(n)$, for many nonnegative multiplicative functions $f$. Summing on $k$ recovers a frequently-used mean-value theorem of Hall and Tenenbaum. We use the same idea to establish a variant of a theorem of Shirokov, concerning multiplicative functions that are $o(1)$ on average at the primes.
Remark: Eq. (3) can be viewed as a special case of Lemma 1 in Tenenbaum's A rate estimate in Billingsley's theorem for the size distribution of large prime factors, Q. J. Math. 51 (2000), 385–403. That lemma is itself a dissected version of the Hall--Tenenbaum mean-value theorem, different from my Corollary 3. Thanks to Régis de la Bretèche and Kevin Ford for making me aware of this.
Sums of proper powers [filler piece]
Amer. Math. Monthly 128 (2020), 40
A proper power is a number of the form $a^b$ where $a,b$ are integers larger than $1$. We show that every $n\ge 28$ is a sum of (exactly) four proper powers.
The maximal size of the $k$-fold divisor function for very large $k$
J. Ramanujan Math. Soc. 25 (2020), 341--345
Let $d_k(n)$ denote the number of ways of writing $n$ as an (ordered) product of $k$ positive integers. When $k=2$, Wigert proved in 1907 that $$ \log d_k(n) \le (1+o(1)) \log k \frac{\log n}{\log \log n} \qquad (n\to\infty). $$ Call this (*). In 1992, Norton showed that (*) holds whenever $k=o(\log{n})$; this is sharp, since (*) holds with equality when $n$ is a product of the first several primes. In this note, we determine the maximal size of $\log d_k(n)$ when $k \gg \log{n}$. To illustrate: Let $\kappa > 0$ be fixed, and let $k,n\to\infty$ in such a way that $k/\log{n}\to\kappa$; then $$ \log d_k(n) \le \Bigg(s+\kappa \sum_{p\text{ prime}} \sum_{\ell \ge 1}\frac{1}{\ell p^{\ell s}} + o(1)\Bigg) \log{n}, $$ where $s >1$ is implicitly defined by $\sum_{p\text{ prime}} \frac{\log {p}}{p^{s}-1} = \frac{1}{\kappa}$. Moreover, this upper bound is optimal for every value of $\kappa$. Our results correct and improve on recent work of Fedorov.
Phi, Primorials, and Poisson
Illinois J. Math. 64 (2020), 319--330
The primorial $p\#$ of a prime $p$ is the product of all primes $q\le p$. Let pr($n$) denote the largest prime $p$ with $p\#\mid\phi(n)$, where $\phi$ is Euler's totient function. We show that the normal order of pr$(n)$ is $\log\log n/\log\log\log n$. That is, pr$(n)\sim\log\log n/\log\log\log n$ as $n\to\infty$ on a set of integers of asymptotic density 1. In fact we show there is an asymptotic secondary term and, on a tertiary level, there is an asymptotic Poisson distribution. We also show an analogous result for the largest integer $k$ with $k!\mid \phi(n)$.
The number of non-cyclic Sylow subgroups of the multiplicative group modulo $n$
Canad. Math. Bull. 64 (2021), 204--215
For each positive integer $n$, let $U(\mathbb{Z}/n\mathbb{Z})$ denote the group of units modulo $n$, which has order $\phi(n)$ (Euler's function) and exponent $\lambda(n)$ (Carmichael's function). The ratio $\phi(n)/\lambda(n)$ is always an integer, and a prime $p$ divides this ratio precisely when the (unique) Sylow $p$-subgroup of $U(\mathbb{Z}/n\mathbb{Z})$ is noncyclic. Write $W(n)$ for the number of such primes $p$. Banks, Luca, and Shparlinski showed that for certain constants $C_1, C_2 >0$, $$ C_1 \frac{\log\log{n}}{(\log\log\log{n})^2} \le W(n) \le C_2 \log\log{n} $$ for all $n$ from a sequence of asymptotic density $1$. We sharpen their result by showing that $W(n)$ has normal order $\log\log{n}/\log\log\log{n}$.
The reciprocal sum of divisors of Mersenne numbers
Acta Arith. 197 (2021), 421--440
We investigate various questions concerning the reciprocal sum of divisors, or prime divisors, of the Mersenne numbers $2^n-1$. Conditional on the Elliott--Halberstam Conjecture and the Generalized Riemann Hypothesis, we determine $\max_{n\le x} \sum_{p \mid 2^n-1} 1/p$ to within $o(1)$ and $\max_{n\le x} \sum_{d\mid 2^n-1}1/d$ to within a factor of $1+o(1)$, as $x\to\infty$. This refines, conditionally, earlier estimates of Erdős and Erdős--Kiss--Pomerance. Conditionally (only) on GRH, we also determine $\sum 1/d$ to within a factor of $1+o(1)$ where $d$ runs over all numbers dividing $2^n-1$ for some $n\le x$. This conditionally confirms a conjecture of Pomerance and answers a question of Murty--Rosen--Silverman. Finally, we show that both $\sum_{p\mid 2^n-1} 1/p$ and $\sum_{d\mid 2^n-1}1/d$ admit continuous distribution functions in the sense of probabilistic number theory.
A quick route to unique factorization in quadratic orders
Amer. Math. Monthly 128 (2021), 554--558
We give a short proof --- not relying on ideal classes or the geometry of numbers --- of a known criterion for quadratic orders to possess unique factorization.
On the stable reduction of hyperelliptic curves
Tohoku Math. J. 74 (2022), 195--213
Let $f: S\to B$ be a surface fibration of genus $g\ge 2$ over $\mathbb{C}$. The semistable reduction theorem asserts there is a finite base change $\pi: B'\to B$ such that the fibration $S\times_BB'\to B'$ admits a semistable model. An interesting invariant of $f$, denoted by $N(f)$, is the minimum of $\deg(\pi)$ for all such $\pi$. In an early paper of Xiao, he gives a uniform multiplicative upper bound $N_g$ for $N(f)$ depending only on the fibre genus $g$. However, it is not known whether Xiao's bound is sharp or not. In this paper, we give another uniform upper bound $N'_g$ for $N(f)$ when $f$ is hyperelliptic. Our $N'_g$ is optimal in the sense that for every $g\ge 2$ there is a hyperelliptic fibration $f$ of genus $g$ so that $N(f)=N_g'$. In particular, Xiao's upper bound $N_g$ is also optimal once $N_g=N'_g$. Finally we show that the last equation $N_g=N_g'$ holds for infinitely many $g$.
Comparing multiplicative orders mod $p$, as $p$ varies
New York J. Math 27 (2021), 600--614
Schinzel and Wójcik have shown that if $\alpha, \beta$ are rational numbers not $0$ or $\pm 1$, then $\text{ord}_p(\alpha)=\text{ord}_p(\beta)$ for infinitely many primes $p$, where $\text{ord}_p(\cdot)$ denotes the order in $\mathbb{F}_p^{\times}$. We begin by asking: When are there infinitely many primes $p$ with $\text{ord}_p(\alpha) > \text{ord}_p(\beta)$? We write down several families of pairs $\alpha,\beta$ for which we can prove this to be the case. In particular, we show this happens for "100%" of pairs $A,2$, as $A$ runs through the positive integers. We end on a different note, proving a version of Schinzel and Wójcik's theorem for the integers of an imaginary quadratic field $K$: If $\alpha, \beta \in \mathcal{O}_K$ are nonzero and neither is a root of unity, then there are infinitely many maximal ideals $P$ of $\mathcal{O}_K$ for which $\text{ord}_P(\alpha) = \text{ord}_P(\beta)$.
Finite sets containing near-primitive roots
J. Number Theory 225 (2021), 360--373
Fix $a \in \mathbb{Z}$, $a\notin \{0,\pm 1\}$. A simple argument shows that for each $\epsilon > 0$, and almost all (asymptotically 100% of) primes $p$, the multiplicative order of $a$ modulo $p$ exceeds $p^{\frac12-\epsilon}$. It is an open problem to show the same result with $\frac12$ replaced by any larger constant. We show that if $a,b$ are multiplicatively independent, then for almost all primes $p$, one of $a,b,ab, a^2b, ab^2$ has order exceeding $p^{\frac{1}{2}+\frac{1}{30}}$. The same method allows one to produce, for each $\epsilon > 0$, explicit finite sets $\mathcal{A}$ with the property that for almost all primes $p$, some element of $\mathcal{A}$ has order exceeding $p^{1-\epsilon}$. Similar results hold for orders modulo general integers $n$ rather than primes $p$.
The distribution of numbers with many factorizations
Math. Z. 299 (2021), 2327--2399
Let $f(m)$ denote the number of factorizations of the positive integer $m$, i.e., the number of ways of writing $m$ as product of integers larger than $1$, where the order of the factors is not taken into account. Let $\epsilon > 0$ and $\alpha \in (0,1)$. We prove that for all $x > x_0(\epsilon,\alpha)$ and every $\mathcal{S} \subset [1,x]$ with $\#\mathcal{S} \le x^{1-\alpha}$, $$ \sum_{m \in \mathcal{S}} f(m) \le x/L(x)^{\alpha-\epsilon}, $$ where $L(x) = \exp(\log x\cdot \log\log\log{x}/\log\log x)$. This generalizes a recent result of the author concerning popular values of Euler's $\phi$-function. We also estimate the $\beta$-th moment of $f(m)$, for all $\beta > 0$.
Numbers which are orders only of cyclic groups
Proc. Amer. Math. Soc. 150 (2022), 515--524
We call $n$ a cyclic number if every group of order $n$ is cyclic. It is implicit in work of Dickson, and explicit in work of Szele, that $n$ is cyclic precisely when $\gcd(n,\phi(n))=1$. With $C(x)$ denoting the count of cyclic $n\le x$, Erdős proved that $$ C(x) \sim e^{-\gamma} x/\log\log\log{x}, \quad\text{as $x\to\infty$}. $$ We show that $C(x)$ has an asymptotic series expansion, in the sense of Poincaré, in descending powers of $\log\log\log{x}$, namely $$ \frac{e^{-\gamma} x}{\log\log\log{x}} \left(1-\frac{\gamma}{\log\log\log{x}} + \frac{\gamma^2 + \frac{1}{12}\pi^2}{(\log\log\log{x})^2} - \frac{\gamma^3 +\frac{1}{4} \gamma \pi^2 + \frac{2}{3}\zeta(3)}{(\log\log\log{x})^3} + \dots \right). $$
The least degree of a CM point on a modular curve
J. London Math. Soc. 105 (2022), 825--883
For a modular curve $X = X_0(N)$, $X_1(N)$ or $X_1(M,N)$ defined over $\mathbb{Q}$, we denote by $d_{\mathrm{CM}}(X)$ the least degree of a CM point on $X$. For each discriminant $\Delta < 0$, we determine the least degree of a point on $X_0(N)$ with CM by the order of discriminant $\Delta$. This places us in a position to study $d_{\mathrm{CM}}(X)$ as an "arithmetic function" and we do so, obtaining various upper bounds, lower bounds and typical bounds. We deduce that all but finitely many curves in each of the families have sporadic CM points. Finally we supplement these results with a computational study, e.g. computing $d_{\mathrm{CM}}(X_0(N))$ and $d_{\mathrm{CM}}(X_1(N))$ exactly for $N \leq 10^6$ and determining whether $X_0(N)$ (resp. $X_1(N)$, resp. $X_1(M,N)$) has sporadic CM points for all but $106$ values of $N$ (resp. $227$ values of $N$, resp. $146$ pairs $(M,N)$ with $M \geq 2$).
A problem in comparative order theory
Period. Math. Hungar. 86 (2023), 24--36
Write $\mathrm{ord}_p(\cdot)$ for the multiplicative order in $\mathbb{F}_p^{\times}$. Recently, Matthew Just and the second author investigated the problem of classifying pairs $\alpha, \beta \in \mathbb{Q}^{\times}\setminus\{\pm 1\}$ for which $\mathrm{ord}_p(\alpha) > \mathrm{ord}_p(\beta)$ holds for infinitely many primes $p$. They called such pairs order-dominant. We describe an easily-checkable sufficient condition for $\alpha,\beta$ to be order-dominant. Via the large sieve, we show that almost all integer pairs $\alpha,\beta$ satisfy our condition, with a power savings on the size of the exceptional set.
Joint distribution in residue classes of polynomial-like multiplicative functions
Acta Arith. 202 (2021), 89--104
Under fairly general conditions, we show that families of integer-valued polynomial-like multiplicative functions are uniformly distributed in coprime residue classes mod $p$, where $p$ is a growing prime (or nearly prime) modulus. This can be seen as complementary to work of Narkiewicz, who obtained comprehensive results for fixed moduli.
Distribution mod $p$ of Euler's totient and the sum of proper divisors
Michigan Math. J. (to appear)
We consider the distribution in residue classes modulo primes $p$ of Euler's totient function $\phi(n)$ and the sum-of-proper-divisors function $s(n):=\sigma(n)-n$. We prove that the values $\phi(n)$, for $n\le x$, that are coprime to $p$ are asymptotically uniformly distributed among the $p-1$ coprime residue classes modulo $p$, uniformly for $5 \le p \le (\log{x})^A$ (with $A$ fixed but arbitrary). We also show that the values of $s(n)$, for $n$ composite, are uniformly distributed among all $p$ residue classes modulo every $p\le (\log{x})^A$. These appear to be the first results of their kind where the modulus is allowed to grow substantially with $x$.
Powerfree sums of proper divisors
Colloq. Math. 168 (2022), 287--295
Let $s(n):= \sum_{d\mid n, d < n} d$ denote the sum of the proper divisors of $n$. It is natural to conjecture that for each integer $k\ge 2$, the equivalence $$ \text{$n$ is $k$th powerfree} \Longleftrightarrow \text{$s(n)$ is $k$th powerfree} $$ holds almost always (meaning, on a set of asymptotic density $1$). We prove this for $k\ge 4$.
Dirichlet, Sierpiński, and Benford
J. Number Theory 239 (2022), 352--364
Sixty years ago, Sierpiński observed that for any positive integers $A$ and $B$, and any $g\ge 2$, there are infinitely many primes whose base $g$-expansion begins with the digits of $A$ and ends with those of $B$. Sierpiński's short proof rests on the prime number theorem for arithmetic progressions (PNT for APs). We explain how his result can be viewed as a natural intermediary between Dirichlet's theorem on primes in progressions and the PNT for APs. In addition to being of pedagogical interest, this perspective quickly yields a generalization of Sierpiński's result where the initial and terminal digits of $p$ are prescribed in two coprime bases simultaneously; moreover, the proportion (Dirichlet density) of the corresponding primes is determined explicitly. The same quasielementary method shows that the arithmetic functions $\phi(n)$, $\sigma(n)$, and $d(n)$ obey "Benford's law" in a suitable sense.
Sums of proper divisors follow the Erdős-Kac law
Proc. Amer. Math. Soc. 151 (2023), 977--988
Let $s(n)=\sum_{d\mid n,~d < n} d$ denote the sum of the proper divisors of $n$. The second-named author proved that $\omega(s(n))$ has normal order $\log\log{n}$, the analogue for $s$-values of a classical result of Hardy and Ramanujan. We establish the corresponding Erdős--Kac theorem: $\omega(s(n))$ is asymptotically normally distributed with mean and variance $\log\log{n}$. The same method applies with $s(n)$ replaced by any of several other unconventional arithmetic functions, such as $\beta(n):=\sum_{p\mid n} p$, $n-\phi(n)$, and $n+\tau(n)$ ($\tau$ being the divisor function).
Benford behavior and distribution in residue classes of large prime factors
Canad. Math. Bull. 66 (2023), 626--642
We investigate the leading digit distribution of the $k$th largest prime factor of $n$ (for each fixed $k=1,2,3,\dots$) as well as the the sum of all prime factors of $n$. In each case, we find that the leading digits are distributed according to Benford's law. Moreover, Benford behavior emerges simultaneously with equidistribution in arithmetic progressions uniformly to small moduli.
On the greatest common divisor of a number and its sum of divisors, II
Number Theory in Memory of Eduard Wirsing, Helmut Maier, Jörn Steuding, Rasa Steuding, eds. Springer Cham (2023)
Let $E(x,y) = \#\{n\le x: \gcd(n,\sigma(n)) > y\}$. We collect known results about the distribution of $E(x,y)$ and establish a new, sharp estimate for $E(x,y)$ when $y$ grows faster than any power of $\log\log{x}$ but $y = \exp((\log\log{x})^{o(1)})$. Taken together, these results determine the order of magnitude of $\log(E(x,y)/x)$ whenever $1 \le y \le x^{1-\epsilon}$.
Distribution in coprime residue classes of polynomially-defined multiplicative functions
Math. Z. 303 (2023), no. 4, paper 93, 20 pages
An integer-valued multiplicative function $f$ is said to be polynomially-defined if there is a nonconstant separable polynomial $F(T)\in \Z[T]$ with $f(p)=F(p)$ for all primes $p$. We study the distribution in coprime residue classes of polynomially-defined multiplicative functions, establishing equidistribution results allowing a wide range of uniformity in the modulus $q$. For example, we show that the values $\phi(n)$, sampled over integers $n \le x$ with $\phi(n)$ coprime to $q$, are asymptotically equidistributed among the coprime classes modulo $q$, uniformly for moduli $q$ coprime to $6$ that are bounded by a fixed power of $\log{x}$.
On Benford's law for multiplicative functions
Proc. Amer. Math. Soc. 151 (2023), 4607--4619
We provide a criterion to determine whether a real multiplicative function is a strong Benford sequence. The criterion implies that the $k$-divisor functions, where $k \ne 10^j$, and Hecke eigenvalues of newforms, such as the Ramanujan tau function, are strong Benford. In contrast to some earlier work, our approach is based on Halász’s Theorem.
Intermediate prime factors in specified subsets
Monatshefte Math. 202 (2023), 837--855
Let $\mathcal{P}$ be a fixed set of primes possessing a limiting frequency $\nu$, as detected by the weight $1/p$. We show that for any fixed $\alpha \in (0,1)$, the $\lceil \alpha \Omega(n) \rceil$-th smallest prime factor of $n$, denoted $P^{(\alpha)}(n)$, belongs to $\mathcal{P}$ on a set of $n$ with natural density $\nu$. We prove a similar result for the largest prime factor $P_{\le y}(n)$ of $n$ not exceeding $y$, whenever $y\to\infty$. As corollaries, $P^{(\alpha)}(n)$ and $P_{\le y}(n)$ conform to Benford's leading digit law. Finally, we establish the equidistribution of $P^{(\alpha)}(n)$ in coprime residue classes, in an essentially optimal range of uniformity in the modulus.
Two problems on the distribution of Carmichael's lambda function
Mathematika 69 (2023), 1195--1220
Let $\lambda(n)$ denote the exponent of the multiplicative group modulo $n$. We show that when $q$ is odd, each coprime residue class modulo $q$ is hit equally often by $\lambda(n)$ as $n$ varies. Under the stronger assumption that $\gcd(q,6)=1$, we prove that equidistribution persists throughout a Siegel--Walfisz-type range of uniformity. By similar methods we show that $\lambda(n)$ obeys Benford's leading digit law with respect to natural density. Moreover, if we assume GRH, then Benford's law holds for the order of $a$ mod $n$, for any fixed integer $a\notin \{0,\pm 1\}$.
Densities of integer sets represented by quadratic forms
J. Number Theory 256 (2024), 290--328
Let $f(t_1,\dots, t_n)$ be a nondegenerate integral quadratic form. We analyze the asymptotic behavior of the function $D_f(X)$, the number of integers of absolute value up to $X$ represented by $f$. When $f$ is isotropic or $n$ is at least 3, we show that there is a $\delta(f) \in \mathbb{Q}\cap (0,1)$ such that $D_f(X) \sim \delta(f) X$ and call $\delta(f)$ the density of $f$. We consider the inverse problem of which densities arise. arise. Our main technical tool is a Near Hasse Principle: a quadratic form may fail to represent infinitely many integers that it locally represents, but this set of exceptions has density $0$ within the set of locally represented integers.
Partitioning powers into sets of equal sum
Rocky Mountain J. Math. (to appear)
For integers $k \ge 1$ and $m \ge 2$, we study the set of integers $n$ for which the set $\{1^k , 2^k , \dots, n^k\}$ can be partitioned into $m$ sets of equal sum. Most of the literature on the problem focuses on finding the least $n$ for which a partition is possible. In our work we focus on finding all $n$ given $k$ and $m$.
Half-factorial real quadratic orders
Arch. Math. (Basel) (to appear)
Recall that $D$ is a half-factorial domain (HFD) when $D$ is atomic and every equation $\pi_1\cdots \pi_k = \rho_1 \cdots\rho_\ell$, with all $\pi_i$ and $\rho_j$ irreducible in $D$, implies $k=\ell$. We explain how techniques introduced to attack Artin's primitive root conjecture can be applied to understand half-factoriality of orders in real quadratic number fields. In particular, we prove that (a) there are infinitely many real quadratic orders that are half-factorial domains, and (b) under the Generalized Riemann Hypothesis, $\mathbb{Q}(\sqrt{2})$ contains infinitely many HFD orders.
$\mathbb{Z}[\sqrt{-5}]$: halfway to unique factorization
Amer. Math. Monthly (to appear)
It is well known that factorization is not unique in $\Z[\sqrt{-5}]$. We give a short, self-contained proof that $\Z[\sqrt{-5}]$ is "halfway" towards being a unique factorization domain: For every nonzero, nonunit $\alpha \in \Z[\sqrt{-5}]$, any two factorizations of $\alpha$ into irreducibles involve the same number of factors.
Talks
HAMLET. 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.
Gaps between primes
-
Gaps between primes: the story so far
UGA number theory seminar, September 2014
-
Big doings with small gaps
American Institute of Mathematics, November 2014. See also: American Association for the Advancement of Science Annual Meeting, February 2015, Invited Address @ Huntsville AMS Southeastern Sectional Meeting, March 2015
Sums of divisors
-
Counting perfect numbers
(UGA number theory seminar, September 2014)
-
The sum of divisors of $n$, modulo $n$
(CNTA 2012)
-
The distribution of sociable numbers
See also: Sociable numbers, or How I messed with perfection and lived to write papers about it (2011 Joint Mathematics Meetings), A perfect storm (U. Missouri, College of Charleston), and Some problems of Erdős on the sum-of-divisors function (Cleveland Area Number Theory Seminar, 2015)
-
Two thousand years of summing divisors (Dartmouth colloquium)
See also: The quest for perfection (Midwest Number Theory Day 2012)
-
The distribution of abundant numbers
(Integers 2013 Conference)
-
Summing divisors: A report on the first 2000 years
(Oberlin Pizza Lunch talk, March 2015)
-
A finiteness theorem for odd perfect numbers
(UGA Grad Student Seminar, June 2020)
See also: Perfection, a brief introduction
-
The frequency of partially perfect numbers
(2023 JMM, BSM special session)
Analytic results on elliptic curves
-
Statistics associated with reductions of elliptic curves modulo $p$
(CRM workshop "New approaches in probabilistic and multiplicative number theory")
-
Two analytic problems about CM elliptic curves
(Stanford, February 2015)
-
Anatomy of torsion in the CM case
(2015 Illinois Number Theory conference, August 2015)
-
$\phi$-nomenology and torsion subgroups of CM elliptic curves
(2016 Gainesville International Number Theory Conference, in honor of K. Alladi's 60th birthday, March 2016)
-
Torsion subgroups of CM elliptic curves
(2017 Joint Meetings; special session on Discrete Structures in Number Theory)
Prime splitting in number fields
Miscellaneous
-
Stretching, the truth about unique factorization
Number Theory Web Seminar; February 2024
-
Unique factorization: what not everyone knows
Dartmouth Colloquium; September 2023
-
Some distribution problems concerning arithmetic functions
LSU Number Theory Seminar; October 2022
-
Uniform and weak uniform distribution of certain arithmetic functions
Combinatorial and Additive Number Theory meeting; May 2022
-
Multiplicative orders mod $p$
Kansas State NTS; March 2021
-
Thoughts on the order of $a$ mod $p$
Luxembourg NTS; October 2020
-
Popular values and popular subsets of Euler's $\varphi$-function
Seminar at MPIM; November 2019. See also: short version for the 2019 JMM.
-
Some algebraic contributions to Waring's problem
2019 Joint Meetings
-
Squares modulo $p$
2018 Joint Meetings. See also: Tufts Algebra, Geometry, and Number Theory seminar version
-
Arithmetic functions: old and new
(for the 2017 MSRI workshop `Recent developments in analytic number theory')
-
Analogies between integers and polynomials
(2013 CIMPA-ICTP summer school, UP Diliman)
-
Prime numbers and prime polynomials
Slides from my thesis defense.
-
Is there a pattern in the prime numbers?
Based on talks at Dartmouth's 2006 Exploring Math Program, the Ross Summer Mathematics Program 2007 reunion conference, and the UGA 2013 summer math camp.
-
Rational cubic reciprocity
See also: Rational (!) cubic and biquadratic reciprocity (Ross Program 2005)
-
N = ☐ + ☐ + ☐
see also: 15-minute version for CNTA 2010
-
The parity of the multiplicative partition function
(2011 Illinois number theory meeting)
-
Solved and unsolved problems in elementary number theory
(Spring 2014 Athens/Atlanta Number Theory Seminar)