Source author record

Nathan McNew

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 math.GT

Catalog footprint

Research overview

12works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Counting pattern-avoiding integer partitions

A partition $α$ is said to contain another partition (or pattern) $μ$ if the Ferrers board for $μ$ is attainable from $α$ under removal of rows and columns. We say $α$ avoids $μ$ if it does not contain $μ$ . In this paper we count the number of partitions of $n$ avoiding a fixed pattern $μ$ , in terms of generating functions and their asymptotic growth rates. We find that the generating function for this count is rational whenever $μ$ is (rook equivalent to) a partition in which any two part sizes differ by at least two. In doing so, we find a surprising connection to metacyclic $p$ -groups. We further obtain asymptotics for the number of partitions of $n$ avoiding a pattern $μ$ . Using these asymptotics we conclude that the generating function for $μ$ is not algebraic whenever $μ$ is rook equivalent to a partition with distinct parts whose first two parts are positive and differ by 1.

preprint2020arXiv

Counting primitive subsets and other statistics of the divisor graph of $\{1,2, \ldots n\}$

Let $Q(n)$ denote the count of the primitive subsets of the integers $\{1,2\ldots n\}$ . We give a new proof that $Q(n) = α^{(1+o(1))n}$ which allows us to give a good error term and to improve upon the lower bound for the value of this constant $α$ . We also show that the method developed can be applied to many similar problems that can be stated in terms of the divisor graph, including other questions about primitive sets, geometric-progression-free sets, and the divisor graph path-cover problem.

preprint2020arXiv

On the Erdős primitive set conjecture in function fields

Erdős proved that $\mathcal{F}(A) := \sum_{a \in A}\frac{1}{a\log a}$ converges for any primitive set of integers $A$ and later conjectured this sum is maximized when $A$ is the set of primes. Banks and Martin further conjectured that $\mathcal{F}(\mathcal{P}_1) > \ldots > \mathcal{F}(\mathcal{P}_k) > \mathcal{F}(\mathcal{P}_{k+1}) > \ldots$ , where $\mathcal{P}_j$ is the set of integers with $j$ prime factors counting multiplicity, though this was recently disproven by Lichtman. We consider the corresponding problems over the function field $\mathbb{F}_q[x]$ , investigating the sum $\mathcal{F}(A) := \sum_{f \in A} \frac{1}{\text{deg} f \cdot q^{\text{deg} f}}$ . We establish a uniform bound for $\mathcal{F}(A)$ over all primitive sets of polynomials $A \subset \mathbb{F}_q[x]$ and conjecture that it is maximized by the set of monic irreducible polynomials. We find that the analogue of the Banks-Martin conjecture is false for $q = 2, 3$ , and $4$ , but we find computational evidence that it holds for $q > 4$ .

preprint2020arXiv

On the size of primitive sets in function fields

A set is primitive if no element of the set divides another. We consider primitive sets of monic polynomials over a finite field and find natural generalizations of many of the results known for primitive sets of integers. In particular we generalize a result of Besicovitch to show that there exist primitive sets in $\mathbb{F}_q[x]$ with upper density arbitrarily close to $\frac{q - 1}{q}$ . Then, for a primitive set $A$ , we consider the sum $\sum_{a \in A} \frac{1}{q^{°a}°a}$ , the natural analogue in this setting of a sum considered by Erdős for primitive subsets of the integers, and show that it is uniformly bounded over all primitive sets $A$ . We end with a generalization of work of Martin and Pomerance on the asymptotic growth rate of the counting function of a primitive set. Along the way we prove a quantitative analogue of the Hardy-Ramanujan theorem for function fields, as well as bounds on the size of the $k$ -th irreducible polynomial.

preprint2020arXiv

Unknotted cycles

Noting that cycle diagrams of permutations visually resemble grid diagrams used to depict knots and links in topology, we consider the knot (or link) obtained from the cycle diagram of a permutation. We show that the permutations which correspond in this way to an unknot are enumerated by the Schröder numbers, and also enumerate the permutations corresponding to an unlink. The proof uses Bennequin's inequality.

preprint2016arXiv

Subsets of $\mathbb{F}_q[x]$ free of 3-term geometric progressions

Several recent papers have considered the Ramsey-theoretic problem of how large a subset of integers can be without containing any 3-term geometric progressions. This problem has also recently been generalized to number fields, determining bounds on the greatest possible density of ideals avoiding geometric progressions. We study the analogous problem over $\mathbb{F}_q[x]$ , first constructing a set greedily which avoids these progressions and calculating its density, and then considering bounds on the upper density of subsets of $\mathbb{F}_q[x]$ which avoid 3-term geometric progressions. This new setting gives us a parameter $q$ to vary and study how our bounds converge to 1 as it changes, and finite characteristic introduces some extra combinatorial structure that increases the tractibility of common questions in this area.

preprint2015arXiv

Geometric-progression-free sets over quadratic number fields

A problem of recent interest has been to study how large subsets of the natural numbers can be while avoiding 3-term geometric progressions. Building on recent progress on this problem, we consider the analogous problem over quadratic number fields. We first construct high-density subsets of the algebraic integers of an imaginary quadratic number field that avoid 3-term geometric progressions. When unique factorization fails or over a real quadratic number field, we instead look at subsets of ideals of the ring of integers. Our approach here is to construct sets "greedily," a generalization of the greedy set of rational integers considered by Rankin. We then describe the densities of these sets in terms of values of the Dedekind zeta function. Next, we consider geometric-progression-free sets with large upper density. We generalize an argument by Riddell to obtain upper bounds for the upper density of geometric-progression-free subsets, and construct sets avoiding geometric progressions with high upper density to obtain lower bounds for the supremum of the upper density of all such subsets. Both arguments depend critically on the elements with small norm in the ring of integers.

preprint2015arXiv

Infinitude of $k$ -Lehmer numbers which are not Carmichael

In this paper, we prove that there are infinitely many $n$ for which $rad(φ(n))|n-1$ but $n$ is not a Carmichael number. Additionally, we prove that for any $k\geq 3$ , there exist infinitely many $n$ such that $φ(n)|(n-1)^k$ but $φ(n)\nmid (n-1)^{k-1}$ . The constructs that we consider here are generalizations of Carmichael and Lehmer numbers, respectively, that were first formulated by Grau and Oller-Marcén.

preprint2015arXiv

Popular values of the largest prime divisor function

We consider the distribution of the largest prime divisor of the integers in the interval $[2,x]$ , and investigate in particular the mode of this distribution, the prime number(s) which show up most often in this list. In addition to giving an asymptotic formula for this mode as $x$ tends to infinity, we look at the set of those prime numbers which, for some value of $x$ , occur most frequently as the largest prime divisor of the integers in the interval $[2,x]$ . We find that many prime numbers never have this property. We compare the set of "popular primes," those primes which are at some point the mode, to other interesting subsets of the prime numbers. Finally, we apply the techniques developed to a similar problem which arises in the analysis of factoring algorithms.

preprint2015arXiv

Ramsey Theory Problems over the Integers: Avoiding Generalized Progressions

Two well studied Ramsey-theoretic problems consider subsets of the natural numbers which either contain no three elements in arithmetic progression, or in geometric progression. We study generalizations of this problem, by varying the kinds of progressions to be avoided and the metrics used to evaluate the density of the resulting subsets. One can view a 3-term arithmetic progression as a sequence $x, f_n(x), f_n(f_n(x))$ , where $f_n(x) = x + n$ , $n$ a nonzero integer. Thus avoiding three-term arithmetic progressions is equivalent to containing no three elements of the form $x, f_n(x), f_n(f_n(x))$ with $f_n \in\mathcal{F}_{\rm t}$ , the set of integer translations. One can similarly construct related progressions using different families of functions. We investigate several such families, including geometric progressions ( $f_n(x) = nx$ with $n > 1$ a natural number) and exponential progressions ( $f_n(x) = x^n$ ). Progression-free sets are often constructed "greedily," including every number so long as it is not in progression with any of the previous elements. Rankin characterized the greedy geometric-progression-free set in terms of the greedy arithmetic set. We characterize the greedy exponential set and prove that it has asymptotic density 1, and then discuss how the optimality of the greedy set depends on the family of functions used to define progressions. Traditionally, the size of a progression-free set is measured using the (upper) asymptotic density, however we consider several different notions of density, including the uniform and exponential densities.

preprint2013arXiv

On sets of integers which contain no three terms in geometric progression

The problem of looking for subsets of the natural numbers which contain no 3-term arithmetic progressions has a rich history. Roth's theorem famously shows that any such subset cannot have positive upper density. In contrast, Rankin in 1960 suggested looking at subsets without three-term geometric progressions, and constructed such a subset with density about 0.719. More recently, several authors have found upper bounds for the upper density of such sets. We significantly improve upon these bounds, and demonstrate a method of constructing sets with a greater upper density than Rankin's set. This construction is optimal in the sense that our method gives a way of effectively computing the greatest possible upper density of a geometric-progression-free set. We also show that geometric progressions in Z/nZ behave more like Roth's theorem in that one cannot take any fixed positive proportion of the integers modulo a sufficiently large value of n while avoiding geometric progressions.

preprint2012arXiv

Radically weakening the Lehmer and Carmichael conditions

Lehmer's totient problem asks if there exist composite integers n satisfying the condition phi(n)|(n-1), (where phi is the Euler-phi function) while Carmichael numbers satisfy the weaker condition lambda(n)|(n-1) (where lambda is the Carmichael universal exponent function). We weaken the condition further, looking at those composite n where each prime divisor of phi(n) also divides n-1. (So rad(phi(n))|(n-1).) While these numbers appear to be far more numerous than the Carmichael numbers, we show that their distribution has the same rough upper bound as that of the Carmichael numbers, a bound which is heuristically tight.

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.

Nathan McNew

Research overview

Is this your work?

12 publications

Counting pattern-avoiding integer partitions

Counting primitive subsets and other statistics of the divisor graph of $\{1,2, \ldots n\}$

On the Erdős primitive set conjecture in function fields

On the size of primitive sets in function fields

Unknotted cycles

Subsets of $\mathbb{F}_q[x]$ free of 3-term geometric progressions

Geometric-progression-free sets over quadratic number fields

Infinitude of $k$ -Lehmer numbers which are not Carmichael

Popular values of the largest prime divisor function

Ramsey Theory Problems over the Integers: Avoiding Generalized Progressions

On sets of integers which contain no three terms in geometric progression

Radically weakening the Lehmer and Carmichael conditions

See the researcher in context

Building this map preview

Nathan McNew

Research overview

Is this your work?

12 publications

Counting pattern-avoiding integer partitions

Counting primitive subsets and other statistics of the divisor graph of {1,2,…n}\{1,2, \ldots n\}{1,2,…n}

On the Erdős primitive set conjecture in function fields

On the size of primitive sets in function fields

Unknotted cycles

Subsets of Fq[x]\mathbb{F}_q[x]Fq​[x] free of 3-term geometric progressions

Geometric-progression-free sets over quadratic number fields

Infinitude of kkk-Lehmer numbers which are not Carmichael

Popular values of the largest prime divisor function

Ramsey Theory Problems over the Integers: Avoiding Generalized Progressions

On sets of integers which contain no three terms in geometric progression

Radically weakening the Lehmer and Carmichael conditions

See the researcher in context

Building this map preview

Counting primitive subsets and other statistics of the divisor graph of $\{1,2, \ldots n\}$

Subsets of $\mathbb{F}_q[x]$ free of 3-term geometric progressions

Infinitude of $k$ -Lehmer numbers which are not Carmichael