Source author record

Carl Pomerance

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NT math.CO

Catalog footprint

Research overview

20works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2026arXiv

Exceptions to the Erd\H os--Straus--Schinzel conjecture

A famous conjecture of Erd\H os and Straus is that for every integer $n\ge2$ , $4/n$ can be represented as $1/x+1/y+1/z$ , where $x,y,z$ are positive integers. This conjecture was generalized to $5/n$ by Sierpiński, and then Schinzel conjectured that for every integer $m\ge4$ there is a bound $n_m$ such that the fraction $m/n$ is the sum of 3 unit fractions for all integers $n\ge n_m$ . Leveraging and generalizing work of Elsholtz and Tao, we show that if $n_m$ exists it must be at least $\exp(m^{1/3+o(1)})$ ; that is, there are numbers $n$ this large for which $m/n$ is not the sum of 3 unit fractions. We prove a weaker, but numerically explicit version of this theorem, showing that for $m\ge 6.52\times10^9$ there is a prime $p\in(m^2,2m^2)$ with $m/p$ not the sum of 3 unit fractions, and report on some extensive numerical calculations that support this assertion with the much smaller bound $m\ge20$ . A result of Vaughan is that for each $m$ , most $n$ 's have $m/n$ representable; we make the dependence on $m$ in this result explicit. In addition, we prove a result generalizing the problem to the sum of $j$ unit fractions.

preprint2022arXiv

Coprime permutations

Let $C(n)$ denote the number of permutations $σ$ of $[n]=\{1,2,\dots,n\}$ such that $\gcd(j,σ(j))=1$ for each $j\in[n]$ . We prove that for $n$ sufficiently large, $n!/3.73^n < C(n) < n!/2.5^n$ .

preprint2022arXiv

Permutations with arithmetic constraints

Let $S_{\rm lcm}(n)$ denote the set of permutations $π$ of $[n]=\{1,2,\dots,n\}$ such that ${\rm lcm}[j,π(j)]\le n$ for each $j\in[n]$ . Further, let $S_{\rm div}(n)$ denote the number of permutations $π$ of $[n]$ such that $j\midπ(j)$ or $π(j)\mid j$ for each $j\in[n]$ . Clearly $S_{\rm div}(n)\subset S_{\rm lcm}(n)$ . We get upper and lower bounds for the counts of these sets, showing they grow geometrically. We also prove a conjecture from a recent paper on the number of "anti-coprime" permutations of $[n]$ , meaning that each $\gcd(j,π(j))>1$ except when $j=1$ .

preprint2021arXiv

A note on Carmichael numbers in residue classes

Improving on some recent results of Matomäki and of Wright, we show that the number of Carmichael numbers to $X$ in a coprime residue class exceeds $X^{1/(6\log\log\log X)}$ for all sufficiently large $X$ depending on the modulus of the residue class.

preprint2021arXiv

Some thoughts on pseudoprimes

We consider several problems about pseudoprimes. First, we look at the issue of their distribution in residue classes. There is a literature on this topic in the case that the residue class is coprime to the modulus. Here we provide some robust statistics in both these cases and the general case. In particular we tabulate all even pseudoprimes to $10^{16}$ . Second, we prove a recent conjecture of Ordowski: the set of integers $n$ which are a pseudoprime to some base which is a proper divisor of $n$ has an asymptotic density.

preprint2020arXiv

Elliptic curves with Galois-stable cyclic subgroups of order 4

Infinitely many elliptic curves over ${\bf Q}$ have a Galois-stable cyclic subgroup of order 4. Such subgroups come in pairs, which intersect in their subgroups of order 2. Let $N_i(X)$ denote the number of elliptic curves over ${\bf Q}$ with at least $i$ pairs of Galois-stable cyclic subgroups of order 4, and height at most $X$ . In this article we show that $N_1(X) = c_{1,1}X^{1/3}+c_{1,2}X^{1/6}+O(X^{0.105})$ . We also show, as $X\to \infty$ , that $N_2(X)=c_{2,1}X^{1/6}+o(X^{1/12})$ , the precise nature of the error term being related to the prime number theorem and the zeros of the Riemann zeta-function in the critical strip. Here, $c_{1,1}= 0.95740\ldots$ , $c_{1,2}=- 0.87125\ldots$ , and $c_{2,1}= 0.035515\ldots$ are calculable constants. Lastly, we show that $N_i(X)=0$ for $i > 2$ (the result being trivial for $i>3$ given that an elliptic curve has 6 cyclic subgroups of order 4).

preprint2020arXiv

On the critical exponent for $k$ -primitive sets

A set of positive integers is primitive (or 1-primitive) if no member divides another. Erdős proved in 1935 that the weighted sum $\sum1/(n \log n)$ for $n$ ranging over a primitive set $A$ is universally bounded over all choices for $A$ . In 1988 he asked if this universal bound is attained by the set of prime numbers. One source of difficulty in this conjecture is that $\sum n^{-λ}$ over a primitive set is maximized by the primes if and only if $λ$ is at least the critical exponent $τ_1 \approx 1.14$ . A set is $k$ -primitive if no member divides any product of up to $k$ other distinct members. One may similarly consider the critical exponent $τ_k$ for which the primes are maximal among $k$ -primitive sets. In recent work the authors showed that $τ_2 < 0.8$ , which directly implies the Erdős conjecture for 2-primitive sets. In this article we study the limiting behavior of the critical exponent, proving that $τ_k$ tends to zero as $k\to\infty$ .

preprint2020arXiv

Residue classes free of values of Euler's function

We characterize which residue classes contain infinitely many totients (values of Euler's function) and which do not. We show that the union of all residue classes that are totient-free has asymptotic density 3/4, that is, almost all numbers that are 2 mod 4 are in a residue class that is totient-free. In the other direction, we show the existence of a positive density of odd numbers m, such that for any $s\ge0$ and any even number $a$ , the residue class $a\pmod{2^sm}$ contains infinitely many totients.

preprint2015arXiv

On integers $n$ for which $X^n-1$ has a divisor of every degree

A positive integer $n$ is called $φ$ -practical if the polynomial $X^n-1$ has a divisor in $\mathbb{Z}[X]$ of every degree up to $n$ . In this paper, we show that the count of $φ$ -practical numbers in $[1, x]$ is asymptotic to $C x/\log x$ for some positive constant $C$ as $x \rightarrow \infty$ .

preprint2014arXiv

A note on square totients

A well-known conjecture asserts that there are infinitely many primes $p$ for which $p - 1$ is a perfect square. We obtain upper and lower bounds of matching order on the number of pairs of distinct primes $p,q \le x$ for which $(p - 1)(q - 1)$ is a perfect square.

preprint2014arXiv

The image of Carmichael's $λ$ -function

We show that the counting function of the set of values of the Carmichael $λ$ -function is $x/(\log x)^{η+o(1)}$ , where $η=1-(1+\log\log 2)/(\log 2)=0.08607...$ .

preprint2012arXiv

On balanced subgroups of the multiplicative group

A subgroup H of G=(Z/dZ)^* is called balanced if every coset of H is evenly distributed between the lower and upper halves of G, i.e., has equal numbers of elements with representatives in (0,d/2) and (d/2,d). This notion has applications to ranks of elliptic curves. We give a simple criterion in terms of characters for a subgroup H to be balanced, and for a fixed integer p, we study the distribution of integers d such that the cyclic subgroup of (Z/dZ)^* generated by p is balanced.

preprint2012arXiv

On sets of integers which are both sum-free and product-free

We consider sets of positive integers containing no sum of two elements in the set and also no product of two elements. We show that the upper density of such a set is strictly smaller than 1/2 and that this is best possible. Further, we also find the maximal order for the density of such sets that are also periodic modulo some positive integer.

preprint2012arXiv

The maximal density of product-free sets in Z/nZ

This paper studies the maximal size of product-free sets in Z/nZ. These are sets of residues for which there is no solution to ab == c (mod n) with a,b,c in the set. In a previous paper we constructed an infinite sequence of integers (n_i)_{i > 0} and product-free sets S_i in Z/n_iZ such that the density |S_i|/n_i tends to 1 as i tends to infinity, where |S_i|$ denotes the cardinality of S_i. Here we obtain matching, up to constants, upper and lower bounds on the maximal attainable density as n tends to infinity.

preprint2011arXiv

On a problem of Arnold: the average multiplicative order of a given integer

For g,n coprime integers, let l_g(n) denote the multiplicative order of g modulo n. Motivated by a conjecture of Arnold, we study the average of l_g(n) as n <= x ranges over integers coprime to g, and x tending to infinity. Assuming the Generalized Riemann Hypothesis, we show that this average is essentially as large as the average of the Carmichael lambda function. We also determine the asymptotics of the average of l_g(p) as p <= x ranges over primes.

preprint2011arXiv

On numbers $n$ dividing the $n$ th term of a linear recurrence

Here, we give upper and lower bounds on the count of positive integers $n\le x$ dividing the $n$ th term of a nondegenerate linearly recurrent sequence with simple roots.

preprint2011arXiv

Product-free sets with high density

We show that there are sets of integers with asymptotic density arbitrarily close to 1 in which there is no solution to the equation ab=c, with a,b,c in the set. We also consider some natural generalizations, as well as a specific numerical example of a product-free set of integers with asymptotic density greater than 1/2.

preprint2010arXiv

Common values of the arithmetic functions phi and sigma

We show that the equation phi(a)=σ(b) has infinitely many solutions, where phi is Euler's totient function and sigma is the sum-of-divisors function. This proves a 50-year old conjecture of Erdos. Moreover, we show that there are infinitely many integers n such that phi(a)=n and sigma(b)=n each have more than n^c solutions, for some c>0. The proofs rely on the recent work of the first two authors and Konyagin on the distribution of primes p for which a given prime divides some iterate of phi at p, and on a result of Heath-Brown connecting the possible existence of Siegel zeros with the distribution of twin primes.

preprint2010arXiv

Primitive sets with large counting functions

A set of positive integers is said to be primitive if no element of the set is a multiple of another. If $S$ is a primitive set and $S(x)$ is the number of elements of $S$ not exceeding $x$ , then a result of Erd\H os implies that $\int_2^\infty (S(t)/t^2\log t) dt$ converges. We establish an approximate converse to this theorem, showing that if $F$ satisfies some mild conditions and $\int_2^\infty (F(t)/t^2\log t) dt$ converges, then there exists a primitive set $S$ with $S(x) \gg F(x)$ .

preprint2004arXiv

The iterated Carmichael λ-function and the number of cycles of the power generator

Iteration of the modular l-th power function f(x) = x^l (mod n) provides a common pseudorandom number generator (known as the Blum-Blum-Shub generator when l=2). The period of this pseudorandom number generator is closely related to λ(λ(n)), where λ(n) denotes Carmichael's function, namely the maximal multiplicative order of any integer modulo n. In this paper, we show that for almost all n, the size of λ(λ(n)) is n/exp((1+o(1))(log log n)^2 log log log n). We conjecture an analogous formula for the k-th iterate of λ. We deduce that for almost all n, the psuedorandom number generator described above has at least exp((1+o(1))(log log n)^2 log log log n) disjoint cycles. In addition, we show that this expression is accurate for almost all n under the assumption of the Generalized Riemann Hypothesis for Kummerian fields. We also consider the number of iterations of λit takes to reduce an integer n to 1, proving that this number is less than (1+o(1))(log log n)/log 2 infinitely often and speculating that log log n is the true order of magnitude almost always.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Carl Pomerance

Research overview

Is this your work?

20 publications

Exceptions to the Erd\H os--Straus--Schinzel conjecture

Coprime permutations

Permutations with arithmetic constraints

A note on Carmichael numbers in residue classes

Some thoughts on pseudoprimes

Elliptic curves with Galois-stable cyclic subgroups of order 4

On the critical exponent for $k$ -primitive sets

Residue classes free of values of Euler's function

On integers $n$ for which $X^n-1$ has a divisor of every degree

A note on square totients

The image of Carmichael's $λ$ -function

On balanced subgroups of the multiplicative group

On sets of integers which are both sum-free and product-free

The maximal density of product-free sets in Z/nZ

On a problem of Arnold: the average multiplicative order of a given integer

On numbers $n$ dividing the $n$ th term of a linear recurrence

Product-free sets with high density

Common values of the arithmetic functions phi and sigma

Primitive sets with large counting functions

The iterated Carmichael λ-function and the number of cycles of the power generator

See the researcher in context

Building this map preview

Carl Pomerance

Research overview

Is this your work?

20 publications

Exceptions to the Erd\H os--Straus--Schinzel conjecture

Coprime permutations

Permutations with arithmetic constraints

A note on Carmichael numbers in residue classes

Some thoughts on pseudoprimes

Elliptic curves with Galois-stable cyclic subgroups of order 4

On the critical exponent for kkk-primitive sets

Residue classes free of values of Euler's function

On integers nnn for which Xn−1X^n-1Xn−1 has a divisor of every degree

A note on square totients

The image of Carmichael's λλλ-function

On balanced subgroups of the multiplicative group

On sets of integers which are both sum-free and product-free

The maximal density of product-free sets in Z/nZ

On a problem of Arnold: the average multiplicative order of a given integer

On numbers nnn dividing the nnnth term of a linear recurrence

Product-free sets with high density

Common values of the arithmetic functions phi and sigma

Primitive sets with large counting functions

The iterated Carmichael λ-function and the number of cycles of the power generator

See the researcher in context

Building this map preview

On the critical exponent for $k$ -primitive sets

On integers $n$ for which $X^n-1$ has a divisor of every degree

The image of Carmichael's $λ$ -function

On numbers $n$ dividing the $n$ th term of a linear recurrence